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 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.

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

Original Publication (with major differences): ICISC 2012

Date: received 12 Nov 2012, last revised 4 Oct 2013

Contact author: chethan0510 at csa iisc ernet in

Available format(s): PDF | BibTeX Citation

Note: An improved security proof using wrappers included.

Version: 20190217:224314 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]