Cryptology ePrint Archive: Report 2012/646

Galindo-Garcia Identity-Based Signature Revisited

Sanjit Chatterjee and Chethan Kamath and Vikas Kumar

Abstract: In Africacrypt 2009, Galindo-Garcia [11] 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 [4] to solve the discrete-log problem (DLP). In this work, we revisit the security argument given in [11]. 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 [11] fails in the standard security model for IBS [1], 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 [2] together with the programming of the random oracles and Coron's technique [7]. 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 signifi cantly tighter than their original counterparts.

Category / Keywords: public-key cryptography / Identity-based signatures, Galindo-Garcia identity-based signature, Schnorr signature, Forking lemma, Discrete-log assumption.

Publication Info: This is the full version of a paper appearing in ICISC 2012.

Date: received 12 Nov 2012

Contact author: chethan0510 at csa iisc ernet in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20121121:154047 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]