Paper 2012/646

Galindo-Garcia Identity-Based Signature, Revisited

Sanjit Chatterjee, Chethan Kamath, and Vikas Kumar


In Africacrypt 2009, Galindo-Garcia proposed a lightweight identity-based signature (IBS) scheme based on the Schnorr signature. The construction is simple and claimed to be the most efficient IBS till date. The security is based on the discrete-log assumption and the security argument consists of two reductions: B1 and B2, both of which use the multiple-forking lemma to solve the discrete-log problem (DLP). In this work, we revisit the security argument given in. Our contributions are two fold: (i) we identify several problems in the original argument and (ii) we provide a detailed new security argument which allows significantly tighter reductions. In particular, we show that the reduction B1 in fails in the standard security model for IBS, while the reduction B2 is incomplete. To remedy these problems, we adopt a two-pronged approach. First, we sketch ways to fill the gaps by making minimal changes to the structure of the original security argument; then, we provide a new security argument. The new argument consists of three reductions: R1, R2 and R3 and in each of them, solving the DLP is reduced to breaking the IBS. R1 uses the general forking lemma together with the programming of the random oracles and Coron's technique. Reductions R2 and R3, on the other hand, use the multiple-forking lemma along with the programming of the random oracles. We show that the reductions R1 and R2 are significantly tighter than their original counterparts.

Note: An improved security proof using wrappers included.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ICISC 2012
Identity-based signaturesGalindo-Garcia identity-based signatureSchnorr signatureForking lemmaDiscrete-log assumption.
Contact author(s)
chethan0510 @ csa iisc ernet in
2013-10-04: revised
2012-11-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjit Chatterjee and Chethan Kamath and Vikas Kumar},
      title = {Galindo-Garcia Identity-Based Signature, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2012/646},
      year = {2012},
      doi = {10.1007/978-3-642-37682-5_32},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.