Abstract
In Africacrypt 2009, Galindo-Garcia [12] 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: \(\mathcal{B}_{1}\) and \(\mathcal{B}_{2}\), 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 [12]. 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 \(\mathcal{B}_{1}\) in [12] fails in the standard security model for IBS [1], while the reduction \(\mathcal{B}_{2}\) 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: \(\mathcal{R}_{1}\), \(\mathcal{R}_{2}\) and \(\mathcal{R}_{3}\) and in each of them, solving the DLP is reduced to breaking the IBS. \(\mathcal{R}_{1}\) uses the general forking lemma [2] together with the programming of the random oracles and Coron’s technique [8]. Reductions \(\mathcal{R}_{2}\) and \(\mathcal{R}_{3}\), on the other hand, use the multiple-forking lemma along with the programming of the random oracles. We show that the reductions \(\mathcal{R}_{1}\) and \(\mathcal{R}_{2}\) are significantly tighter than their original counterparts.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bellare, M., Namprempre, C., Neven, G.: Security proofs for identity-based identification and signature schemes. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 268–286. Springer, Heidelberg (2004)
Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, pp. 390–399. ACM, New York (2006)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS 1993, pp. 62–73. ACM, New York (1993)
Boldyreva, A., Palacio, A., Warinschi, B.: Secure proxy signature schemes for delegation of signing rights. Journal of Cryptology 25, 57–115 (2012)
Boneh, D., Boyen, X.: Efficient selective-id secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Chatterjee, S., Kamath, C., Kumar, V.: Galindo-Garcia identity-based signature revisited. Cryptology ePrint Archive, Report 2012/646 (2012)
Choon, J., Cheon, J.H.: An identity-based signature from gap Diffie-Hellman groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2002)
Coron, J.-S.: On the exact security of full domain hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)
Sharmila Deva Selvi, S., Sree Vivek, S., Pandu Rangan, C.: Identity-based deterministic signature scheme without forking-lemma. In: Iwata, T., Nishigaki, M. (eds.) IWSEC 2011. LNCS, vol. 7038, pp. 79–95. Springer, Heidelberg (2011)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Galindo, D.: Boneh-franklin identity based encryption revisited. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 791–802. Springer, Heidelberg (2005)
Galindo, D., Garcia, F.D.: A Schnorr-like lightweight identity-based signature scheme. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 135–148. Springer, Heidelberg (2009)
Guillou, L.C., Quisquater, J.-J.: A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 216–231. Springer, Heidelberg (1990)
Herranz, J.: Deterministic identity-based signatures for partial aggregation. The Computer Journal 49(3), 322–330 (2005)
Hess, F.: Efficient identity based signature schemes based on pairings. In: Nyberg, K., Heys, H. (eds.) SAC 2002. LNCS, vol. 2595, pp. 310–324. Springer, Heidelberg (2003)
Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13, 361–396 (2000)
Radhakishan, V., Selvakumar, S.: Prevention of man-in-the-middle attacks using id-based signatures. In: Second International Conference on Networking and Distributed Computing - ICNDC 2011, pp. 165–169 (2011)
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Shoup, V.: OAEP reconsidered. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 239–259. Springer, Heidelberg (2001)
Xie, M., Wang, L.: One-round identity-based key exchange with perfect forward security. Information Processing Letters 112(14-15), 587–591 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chatterjee, S., Kamath, C., Kumar, V. (2013). Galindo-Garcia Identity-Based Signature Revisited. In: Kwon, T., Lee, MK., Kwon, D. (eds) Information Security and Cryptology – ICISC 2012. ICISC 2012. Lecture Notes in Computer Science, vol 7839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37682-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-37682-5_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37681-8
Online ISBN: 978-3-642-37682-5
eBook Packages: Computer ScienceComputer Science (R0)