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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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.
- [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}.
- [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.
- [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.
- [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
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
assumptions (3)
- standard math Bilinearity and non-degeneracy of pairings e: G1 x G2 to GT, and the standard hash-to-group construction.
- domain assumption All five identity-based signature schemes are secure under their published hardness assumptions and random-oracle or standard-model conditions.
- 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.
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.
Reference graph
Works this paper leans on
-
[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
work page 2013
-
[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
work page 2005
-
[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
work page 2001
-
[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
work page 2003
-
[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
work page 2011
-
[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
work page 2006
-
[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]
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
work page 2000
Show all 22 references
-
[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
2018
-
[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
2013
-
[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
2009
-
[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
2001
-
[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
2008
-
[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
2002
-
[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
2006
-
[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
2000
-
[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
2000
-
[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
2003
-
[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
1984
-
[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
2005
-
[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
2014
-
[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...
2003
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.