Galindo-Garcia Identity-Based Signature, Revisited

Sanjit Chatterjee; Chethan Kamath; Vikas Kumar

Paper 2012/646

Galindo-Garcia Identity-Based Signature, Revisited

Sanjit Chatterjee, Chethan Kamath, and Vikas Kumar

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ICISC 2012
DOI: 10.1007/978-3-642-37682-5_32
Keywords: Identity-based signatures Galindo-Garcia identity-based signature Schnorr signature Forking lemma Discrete-log assumption.
Contact author(s): chethan0510 @ csa iisc ernet in
History: 2013-10-04: revised; 2012-11-21: received; See all versions
Short URL: https://ia.cr/2012/646
License: CC BY

BibTeX

@misc{cryptoeprint:2012/646,
      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},
      url = {https://eprint.iacr.org/2012/646}
}