Pith. sign in

REVIEW 2 major objections 5 minor 22 references

Systematization of Knowledge and Implementation: Short Identity-Based Signatures

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read This paper argues that identity-based signatures become much shorter when the pairing curve has small group elements and the signature's point and hash components are compressed, with the Schnorr-type Sakai-Kasahara scheme reaching 40…

desk verdict A competent survey of IBS schemes and JPBC curve sizes, but the paper's only novel size-shortening method is mathematically invalid; reject, but the survey part may be salvageable. read the letter →

arxiv 1908.05366 v1 pith:4XOEBV3N submitted 2019-08-14 cs.CR

classification cs.CR
keywords identity-basedsignaturespairing-basedcryptographyshortpointcompressionsignaturesizepairingcurvesSchnorr-typesyntheticDNAauthentication
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Identity-based signatures are usually compared by security, but this paper treats signature size as the design target: it surveys a set of pairing-based signature schemes, measures how each curve's group-element sizes determine the byte length of each signature, and proposes two generic shrinkages. The first is elliptic-curve point compression: a point $(x,y)$ can be sent as $x$ plus one parity byte, because the curve equation $y^2 = x^3 + ax + b$ recovers $y$, cutting a $G_1$ component from $2n$ bytes to $n+1$. The second is specific to the Sakai-Kasahara Schnorr analogue: the paper claims the hash $h$ in the signature $(h,S)$ can be replaced by $R = h \bmod r$, on the grounds that the verifier's scalar multiplication only sees $h$ modulo the group order $r$. Together these methods produce the paper's headline numbers: the shortest listed signatures fall to 40 bytes on the type-G curve, and several schemes drop below 50 bytes. The concrete motivation is applications that need very short signatures, such as the paper's earlier proposal for signing synthetic DNA.

What carries the argument

The load-bearing object is the signature tuple, whose entries are elements of the two source groups $G_1$ and $G_2$ of the bilinear pairing, of the scalar ring $Z_r$, or of a hash; the byte size of each entry is fixed by the curve parameters (the prime $q$, group order $r$, and embedding degree $k$), so the whole comparison reduces to reading element sizes off a curve table. The two mechanisms doing the work are point compression (the curve equation $y^2 = x^3 + ax + b$ determines $y$ from $x$ up to sign, so one parity bit plus $x$ encodes a point) and hash reduction modulo the group order, which the paper applies to the Sakai-Kasahara Schnorr signature by replacing $h$ with $R = h \bmod r$ because the verification scalar multiplication $-hP_2$ acts through $Z_r$. The second mechanism is what makes the Schnorr analogue uniquely small; without it, the 32-byte full hash would dominate that signature's size.

What would settle it

Run the paper's verification procedure on a shortened Schnorr signature: sign one message, store $(R,S)$ with $R = h \bmod r$, and try to verify using the published check $H_1(m \| w) = h$; because the verifier receives only $R$, it cannot reconstruct $h$, so the check must be weakened to a residue comparison. To settle the claim, find two distinct messages whose hashes are congruent modulo $r$ and show the same $(R,S)$ verifies for both, which would demonstrate that the shortened signature is no longer bound to a single message.

Watch

Extended reading notes

Core claim

On its own terms, the paper's contribution is a size taxonomy plus two compression rules. For each scheme (Sakai-Ohgishi-Kasahara, Paterson, Sakai-Kasahara in both El-Gamal and Schnorr forms, Xun Yi, and the already-implemented Cha-Cheon and Paterson-Schuldt), the signature is a tuple of group elements, and the paper determines the byte cost of each element from the curve's prime size and embedding degree. The first compression rule is universal: any $G_1$ point in a signature can be stored as its $x$-coordinate plus one parity byte, since the curve equation recovers $y$, so a $2n$-byte $G_1$ component becomes $n+1$ bytes. The second rule targets the Schnorr analogue, whose signature is $(h, S)$: because verification computes $-hP_2$ and scalar multiplication reduces the scalar modulo $r$, the paper asserts that $h$ may be stored as $R = h \bmod r$, an element of $Z_r$, rather than as a full 32-byte hash. The paper then tabulates the resulting sizes across the seven curve types and concludes that the compressed Schnorr analogue is the shortest scheme, at 40 bytes on the 149-bit type-G curve and 41 bytes on the type-F and d159 curves.

Load-bearing premise

The load-bearing assumption is that the verifier's computation of $-h$ times a group point sees only the remainder of $h$ modulo the group order, so the signer may send $h \bmod r$ instead of the full hash; if verification must compare the full hash value, the second shortening method fails.

Editorial extensions

If this is right

  • On the paper's tables, the shortest identity-based signature is the compressed Sakai-Kasahara Schnorr analogue at 40 bytes on the type-G curve and 41 bytes on the type-F and d159 curves, down from 70 to 72 bytes uncompressed.
  • For every scheme whose signature contains a $G_1$ point, point compression alone cuts that component from $2n$ to $n+1$ bytes and applies even to schemes already built into the libraries, such as Cha-Cheon and Paterson-Schuldt.
  • For the DNA-signature application, pairing-based signatures plus compression bring a signature from 128 bytes (512 DNA base pairs) down to about 40 to 41 bytes (160 to 164 base pairs).
  • Decompression depends on the curve: the paper notes a simple square-root formula when the prime satisfies $p \equiv 3 \pmod 4$ and a more general routine otherwise, so an implementation must dispatch on curve type.
  • If $G_2$ elements could also be compressed, the schemes that carry a $G_2$ entry (Sakai-Ohgishi-Kasahara, Paterson, Sakai-Kasahara El-Gamal) would shrink further; the paper leaves that as future work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The hash-reduction rule, if valid, would generalize as a design principle: any signature component that enters verification only through scalar multiplication in a prime-order group can be stored as its residue modulo $r$, but each scheme must be checked because verification often also compares hash outputs directly.
  • The 40-byte figure depends on the specific library curves; regenerating curves at the same bit sizes with different primes could change decompression performance (especially for primes $\equiv 1 \pmod 4$) without changing byte sizes, so the size ranking is stable while the timing ranking may not be.
  • A direct experiment can isolate the riskiest step: implement the compressed Schnorr analogue and verify a batch of signatures; if any signature produced by the shortened signer fails verification, the failure points to the replacement of $h$ by $h \bmod r$.
  • The taxonomy suggests a design rule for future identity-based signature schemes: keep $G_2$ elements out of the signature, since they are the largest entries in asymmetric pairings, and prefer constructions whose only group component is a compressed $G_1$ point.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper surveys identity-based signature (IBS) schemes in the context of the JPBC pairing library, tabulates group element sizes for several pairing-friendly curve types, and presents signature-size calculations for six schemes (Sakai–Ohgishi–Kasahara, Paterson, Sakai–Kasahara ElGamal and Schnorr analogs, Xun Yi, plus the library-implemented Cha–Cheon and Paterson–Schuldt). It then proposes two methods to further reduce signature size: point compression of G1 elements (discarding the y-coordinate and storing a one-byte prefix) and hash-component shortening for the Sakai–Kasahara Schnorr scheme, either by truncating the hash to 20 bytes or by replacing it with its residue modulo the group order r. The paper concludes that the compressed Sakai–Kasahara Schnorr scheme gives the shortest signatures.

Significance. The survey and the size tables are useful practical references for implementors choosing pairing curves and IBS schemes. The point-compression technique, if implemented as described, is a standard and valid method, and the paper provides Java code for it. However, the proposed hash-compression methods are not fully sound as presented: the modulo-r method is invalid because the verifier cannot reconstruct the hash from its residue, and the truncation method needs an explicit redefinition of the verification equation. The algebraic verification steps for the underlying schemes are mostly correct, though some proof notation is sloppy. Since the paper's core contribution includes the shortening methods, the correctness issues must be fixed before the paper can be accepted.

major comments (2)
  1. [Section 4, paragraph 'When computing the verification step - en(CA, -hP2)'] The claim that the Sakai–Kasahara Schnorr signature (h,S) can be rewritten as (R,S) with R = h mod r is incorrect. In the verification procedure of Section 3.3, the verifier computes w = en(S,g2) * en(CA, -hP2) and then checks H1(m||w) == h. If the signature is changed to (R,S), the scalar multiplication can use R only because -hP2 = -(h mod r)P2, so the recomputed w matches the signer's e. However, the verifier cannot check H1(m||w) == h because h is not transmitted and cannot be recovered from R. If the check is changed to H1(m||w) == R, the equality holds only with negligible probability (r/2^|H1|). Therefore this proposed method does not yield a valid signature, and the corresponding size reductions claimed in the text and reflected in Table 7 are unachievable under the stated verification algorithm.
  2. [Section 4, Ethereum-style hash truncation] The alternative hash-shortening method (truncating H1 to 20 bytes) is not fully specified. The paper states that the hash value can be shortened 'using the techniques that are used to generate Ethereum or Bitcoin addresses' but does not give the modified verification algorithm. If h is replaced by h' = truncate20(H1(m||e)), then the verification step in Section 3.3 must be changed to compare H1'(m||w) with h', where H1' is the truncated function. Without this explicit modification, the scheme is under-specified, and the 20-byte hash entries in Table 7 for the Schnorr scheme are not tied to a defined algorithm. The paper should define H1' and state the resulting sign and verify procedures.
minor comments (5)
  1. [Section 3.3, Sakai–Kasahara ElGamal analogue] Step 4 computes h1 = H(ZA), but h1 is never used in the signature or verification; only h and xza appear. This unused variable should be removed or the description corrected.
  2. [Sections 3.2 and 3.4, proof equations] In the Paterson and Xun Yi proofs, the notation en(g1,g2)^{h0+VA*h1} and en(g1,g2)^{(r+h*CA)*x} uses group elements (VA, CA) as exponents, which is mathematically ill-formed. Replace these with the correct bilinearity steps, e.g., en(VA,g2)^{h1} = en(CA,P2)^{h1}.
  3. [Section 4, point compression description] The sentence 'If Y is odd we append 02 before X value. If Y is odd we append 03.' contains a typo; the second condition should read 'If Y is even we append 03.' The accompanying Java code is correct.
  4. [Table 7, Sakai–Kasahara Schnorr row] The 'with compression' hash size is listed as 20 bytes for every curve, including d201 (where |r| = 23 bytes) and a1 (where |r| = 128 bytes). This is consistent with fixed 20-byte truncation but not with the R = h mod r method; the text should clarify which hash-compression variant is being used in the table.
  5. [Section 2, type D curves] Only the d159 parameters are given in the body; the bit-lengths for d201 and d224 appear in Table 1 but the text does not state them explicitly. Adding a sentence would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the paper's derivations are arithmetic and standard-pairing identities; its only self-citation is motivational.

full rationale

The central sizing results in Tables 2-7 are obtained by adding the group-element sizes listed in Table 1, which are read off publicly available curve parameters; no parameter is fitted to the reported output sizes. The point-compression claim in Section 4 follows from the curve equation y^2 = x^3 + ax + b and is a standard technique, and the proposed (n+1)-byte representation is stated as a direct consequence of storing only an x-coordinate plus a parity byte. The scheme descriptions in Section 3 are transcriptions of previously published constructions (Sakai-Ohgishi-Kasahara, Paterson, Sakai-Kasahara, Xun-Yi) with their verification equalities restated. The only self-citation, Kar et al. [9], appears as motivation for short signatures and as a numerical comparison in the conclusion; it is not used to justify any derivation or to exclude alternative constructions. The Section 4 hash-residue shortening (R = h mod r) is not circular, although it is unsound as a signature modification because verification compares H1(m || w) to the original hash; unsoundness is a correctness concern, not a reduction of the claimed result to its own input. Accordingly, no step in the claimed derivation chain is equivalent to its inputs by construction, and the paper is best characterized as having no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted in this paper. The size tables are deterministic arithmetic from JPBC property files. The main non-standard assumption injected by the authors is that hash values can be replaced by residues modulo r while preserving verification, which is false and is flagged under weakest_assumption.

assumptions (3)
  • standard math Bilinearity and non-degeneracy of pairings e: G1 x G2 to GT, and the standard hash-to-group construction.
    Section 1 and the verification equations in Section 3 rely on pairing properties and on H mapping strings into G1; these are standard background, not proved in the paper.
  • domain assumption All five identity-based signature schemes are secure under their published hardness assumptions and random-oracle or standard-model conditions.
    The paper imports correctness and security from the original scheme papers without independent proof; the central size comparison assumes these schemes behave as specified.
  • standard math Every G1 element is an affine point (x,y) on y^2 = x^3 + ax + b over F_q with q an odd prime, so y can be recovered from x plus one parity bit.
    Section 4's point compression assumes this curve form and the existence of square roots modulo q; decompression code relies on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Systematization of Knowledge and Implementation: Short Identity-Based Signatures." pith.science (2026). https://pith.science/paper/4XOEBV3N

@misc{pith2026190805366,
  author       = {Pith},
  title        = {Pith review of: Systematization of Knowledge and Implementation: Short Identity-Based Signatures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4XOEBV3N}},
  note         = {Machine review of arXiv:1908.05366}
}
read the original abstract

Identity-Based signature schemes are gaining a lot of popularity every day. Over the last decade, there has been a lot of schemes that have been proposed. Several libraries are there that implement identity-based cryptosystems that include identity-based signature schemes like the JPBC library which is written in Java and the charm-crypto library written in python. However, these libraries do not contain all of the popular schemes, rather the JPBC library contains only one identity-based signature scheme and the charm-crypto contains three. Furthermore, the implemented schemes are designed to work on one particular pairing curve. In pairing-based cryptosystems, even for a given signature scheme, the size of the signature and the performance i.e. the time to sign and verify depends on the chosen pairing curve. There are many applications in which the signature size is of more importance than the performance and similarly other applications where the performance is of more importance than signature size. In this work, we describe the popular signature schemes and their implementation using the JPBC library and describe how different pairing curves affect the signature size and performance. We also provide two methods to further shorten the signature size which is not present in the libraries by default.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Akinyele, Christina Garman, Ian Miers, Matthew W

    Joseph A. Akinyele, Christina Garman, Ian Miers, Matthew W. Pag ano, Michael Rushanan, Matthew Green, and Aviel D. Rubin. Charm: A Fr ame- 16 work for Rapidly Prototyping Cryptosystems. Journal of Cryptographic Engineering, 3(2):111–128, 2013

  2. [2]

    Pairing-Friendly Elliptic Cur ves of Prime Order

    Paulo SLM Barreto and Michael Naehrig. Pairing-Friendly Elliptic Cur ves of Prime Order. In International Workshop on Selected Areas in Cryptog- raphy, pages 319–331. Springer, 2005

  3. [3]

    Identity-Based Encryption from t he Weil Pairing

    Dan Boneh and Matt Franklin. Identity-Based Encryption from t he Weil Pairing. In Proceedings of the Annual International Cryptology Confer ence, pages 213–229. Springer, 2001

  4. [4]

    An Identity-Based Signatur e from Gap Diffie-Hellman Groups

    Jae Cha Choon and Jung Hee Cheon. An Identity-Based Signatur e from Gap Diffie-Hellman Groups. In International workshop on public key cryp- tography, pages 18–30. Springer, 2003

  5. [5]

    Jpbc: Java Pairing Based Cry ptog- raphy

    Angelo De Caro and Vincenzo Iovino. Jpbc: Java Pairing Based Cry ptog- raphy. In Computers and communications (ISCC), 2011 IEEE Symposium on, pages 850–855. IEEE, 2011

  6. [6]

    Constructing Pairing-Friendly Elliptic Curves with E m- bedding Degree 10

    David Freeman. Constructing Pairing-Friendly Elliptic Curves with E m- bedding Degree 10. In International Algorithmic Number Theory Sympo- sium, pages 452–465. Springer, 2006

  7. [7]

    Efficient Identity Based Signature Schemes Based o n Pairings

    Florian Hess. Efficient Identity Based Signature Schemes Based o n Pairings. In International Workshop on Selected Areas in Cryptography , pages 310–

  8. [8]

    A One Round Protocol for Tripartite Diffie–Hellman

    Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. In International Algorithmic Number Theory Symposium , pages 385–393. Springer, 2000

Show all 22 references
  1. [9]

    Digital Signatures to Ensure the Authenticity and Integrity of Syn thetic DNA Molecules

    Diptendu Mohan Kar, Indrajit Ray, Jenna Gallegos, and Jean Pec coud. Digital Signatures to Ensure the Authenticity and Integrity of Syn thetic DNA Molecules. In Proceedings of the New Security Paradigms Workshop, Windsor, UK , NSPW ’18, pages 110–122. ACM, 2018

  2. [10]

    The Pairing-Based Cryptography Library

    Ben Lynn et al. The Pairing-Based Cryptography Library. Inte rnet: crypto.stanford.edu/pbc/[Mar. 27, 2013], 2006

  3. [11]

    An Introduction to Pairing-Based Cryptogra phy

    Alfred Menezes. An Introduction to Pairing-Based Cryptogra phy. Recent trends in cryptography , 477:47–65, 2009

  4. [12]

    New Explicit Conditions of Elliptic Curve Traces for FR-Reduction

    Atsuko Miyaji, Masaki Nakabayashi, and Shunzou Takano. New Explicit Conditions of Elliptic Curve Traces for FR-Reduction. IEICE Transactions on Fundamentals of Electronics, Communications and Comput er Sciences, 84(5):1234–1243, 2001

  5. [13]

    Bitcoin: A Peer-to-Peer Electronic Ca sh System

    Satoshi Nakamoto et al. Bitcoin: A Peer-to-Peer Electronic Ca sh System. 2008. 17

  6. [14]

    Id-Based Signatures from Pairings on Ellip tic Curves

    Kenneth G Paterson. Id-Based Signatures from Pairings on Ellip tic Curves. Electronics Letters, 38(18):1025–1026, 2002

  7. [15]

    Efficient Identity-B ased Sig- natures Secure in the Standard Model

    Kenneth G Paterson and Jacob CN Schuldt. Efficient Identity-B ased Sig- natures Secure in the Standard Model. In Australasian Conference on Information Security and Privacy , pages 207–222. Springer, 2006

  8. [16]

    Cryptosystems Based on Pa iring, SCIS 2000-C20, Jan

    R Sakai, K Ohgishi, and M Kasahara. Cryptosystems Based on Pa iring, SCIS 2000-C20, Jan. 2000. Okinawa, Japan

  9. [17]

    Cryptosystems Based on Pairing

    Ryuichi Sakai and Masao Kasahara. Cryptosystems Based on Pairing. In Proceedings of the Symposium on Cryptography and Informati on Security, Okinawa, Japan , January 2000

  10. [18]

    Id Based Cryptosystems with Pairing on Elliptic Curve

    Ryuichi Sakai and Masao Kasahara. Id Based Cryptosystems with Pairing on Elliptic Curve. IACR Cryptology ePrint Archive , 2003:54, 2003

  11. [19]

    Identity-Based Cryptosystems and Signature Sc hemes

    Adi Shamir. Identity-Based Cryptosystems and Signature Sc hemes. In Advances in Cryptology , Lecture Notes in Computer Science, pages 47–53. Springer, Berlin, Heidelberg, August 1984

  12. [20]

    Efficient Identity-Based Encryption without Ra ndom Ora- cles

    Brent Waters. Efficient Identity-Based Encryption without Ra ndom Ora- cles. In Annual International Conference on the Theory and Applicat ions of Cryptographic Techniques, pages 114–127. Springer, 2005

  13. [21]

    Ethereum: A Secure Decentralised Generalised Trans- action Ledger

    Gavin Wood et al. Ethereum: A Secure Decentralised Generalised Trans- action Ledger. Ethereum project yellow paper, 2014

  14. [22]

    ); BigInteger Xcord = new BigInteger(1,xbytes); BigInteger Ycord = new BigInteger(1,ybytes); String prefix = null; if((Ycord.mod(TWO)).compareTo(BigInteger.ZERO) == 0) { prefix =

    Xun Yi. An Identity-Based Signature Scheme from the Weil Pairin g. IEEE communications letters, 7(2):76–78, 2003. Appendix - Point compression and decompres- sion code in Java private static String pointcompress(Element elem) { // TODO Auto-generated method stub byte[] elembyt...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.