On the generic construction of identity-based signatures with additional properties

David Galindo; Javier Herranz; Eike Kiltz

doi:10.3934/amc.2010.4.453

Article Contents

2010, Volume 4, Issue 4: 453-483. Doi: 10.3934/amc.2010.4.453

This issue Previous Article On cycle-free lattices with high rate label codes Next Article Efficient list decoding of a class of algebraic-geometry codes

On the generic construction of identity-based signatures with additional properties

1.
University of Luxembourg, L-1359, Luxembourg
2.
Dept. Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Barcelona, 08034
3.
Ruhr-University Bochum, Bochum, D-44780

Received: October 31, 2009

Published: October 2010

Abstract Related Papers Cited by

Abstract

It has been stated / demonstrated by Shamir (Crypto 1984) / Bellare, Neven, and Namprempre (Eurocrypt 2004) that identity-based signature schemes can be generically constructed from standard digital signature schemes. In this paper we consider the following natural extension: is there a generic construction of "identity-based signature schemes with additional properties'' (such as identity-based blind signatures, verifiably encrypted signatures, ...) from standard signature schemes with the same properties? Our results show that this is possible for a number of properties including proxy signatures; (partially) blind signatures; verifiably encrypted signatures; undeniable signatures; forward-secure signatures; (strongly) key insulated signatures; online/offline signatures; threshold signatures; and (with some limitations) aggregate signatures.
Using well-known results for standard signature schemes, we conclude that explicit identity-based signature schemes with additional properties can be constructed, enjoying sometimes better properties than specific schemes proposed until now. In particular, our work implies the existence of identity-based signatures with additional properties that are provably secure in the standard model, do not need bilinear pairings, or can be based on general assumptions.

Keywords:

Signatures with additional properties,
identity-based cryptography.

Mathematics Subject Classification: Primary: 94A60; Secondary: 68P25, 03F20.

Citation:

Related Papers

Cited by

References

[1]	IEEE P1363.3: Standard for identity-based cryptographic techniques using pairings.
[2]	M. Abdalla, C. Namprempre and G. Neven, On the (im)possibility of blind message authentication codes, in "Proceedings of CT-RSA'06" (ed. D. Pointcheval), Springer-Verlag, (2006), 262-279.
[3]	M. Abe and E. Fujisaki, How to date blind signatures, in "Proceedings of Asiacrypt'96" (eds. K. Kim and T. Matsumoto), Springer-Verlag, (1996), 244-251.
[4]	M. Abe and T. Okamoto, Provably secure partially blind signatures, in "Proceedings of Crypto'00" (ed. M. Bellare), Springer-Verlag, (2000), 271-286.
[5]	J. H. Ahn, M. Green and S. Hohenberger, Synchronized aggregate signatures: neew definitions, constructions and applications, in "Proceedings of CCS'10," to appear, ACM Press, (2010); available online at http://eprint.iacr.org/2010/422.
[6]	S. S. Al-Riyami and K. G. Paterson, Certificateless public key cryptography, in "Proceedings of Asiacrypt'03" (ed. C.S. Laih), Springer-Verlag, (2003), 452-473.
[7]	G. Ateniese and B. De Medeiros, Identity-based chameleon hash and applications, in "Proceedings of Financial Cryptography'04" (ed. A. Juels), Springer-Verlag, (2004), 164-180.
[8]	J. Baek and Y. Zheng, Identity-based threshold signature scheme from the bilinear pairings, in "Proceedings of ITCC'04 (1)," IEEE Computer Society, (2004), 124-128.
[9]	M. Bellare and S. K. Miner, A forward-secure digital signature scheme, in "Proceedings of Crypto'99" (ed. M.J. Wiener), Springer-Verlag, (1999), 431-448.
[10]	M. Bellare, C. Namprempre and G. Neven, Security proofs for identity-based identification and signature schemes, Journal of Cryptology, 22 (2009), 1-61.doi: 10.1007/s00145-008-9028-8.
[11]	M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko, The one-more-rsa-inversion problems and the security of chaum's blind signature scheme, Journal of Cryptology, 16 (2003), 185-215.doi: 10.1007/s00145-002-0120-1.
[12]	M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in "Proceedings of CCS'93," ACM Press, (1993), 62-73.
[13]	A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme, in "Proceedings of PKC'03" (ed. Y. Desmedt), Springer-Verlag, (2002), 31-46.
[14]	A. Boldyreva, C. Gentry, A. O'Neill and D. H. Yum, Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing, in "Proceedings of CCS'07" (eds. F. Bao and S. Miller), ACM Press, (2007), 276-285.
[15]	A. Boldyreva, A. Palacio, and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Technical report, available online at http://eprint.iacr.org/2003/096.
[16]	D. Boneh and X. Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups, Journal of Cryptology, 21 (2008), 149-177.doi: 10.1007/s00145-007-9005-7.
[17]	D. Boneh and M. K. Franklin, Identity based encryption from the Weil pairing, SIAM Journal on Computing, 32 (2003), 586-615.doi: 10.1137/S0097539701398521.
[18]	D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in "Proceedings of Eurocrypt'03" (ed. E. Biham), Springer-Verlag, (2003), 416-432.
[19]	D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004), 297-319.doi: 10.1007/s00145-004-0314-9.
[20]	J. Camenisch, M. Koprowski and B. Warinschi, Efficient blind signatures without random oracles, in "Proceedings of SCN'04" (eds. C. Blundo and S. Cimato), Springer-Verlag, (2004), 134-148.
[21]	R. Canneti, O. Goldreich and S. Halevi, The random oracle methodology, revisited, Journal of the ACM, 51 (2004), 557-594.doi: 10.1145/1008731.1008734.
[22]	D. Chaum, Blind signatures for untraceable payments, in "Proceedings of Crypto'82" (eds. D. Chaum, R.L. Rivest and A.T. Sherman), Plenum Press, (1983), 199-203.
[23]	D. Chaum, Designated confirmer signatures, in "Proceedings of Eurocrypt'94" (ed. A. De Santis), Springer-Verlag, (1995), 86-91.
[24]	D. Chaum and H. Van Antwerpen, Undeniable signatures, in "Proceedings of Crypto'89" (ed. G. Brassard), Springer-Verlag, (1989), 212-216.
[25]	X. Cheng, J. Liu and X. Wang, An identity-based signature and its threshold version, in "Proceedings of AINA'05," IEEE Computer Society, (2005), 973-977.
[26]	X. Cheng, J. Liu and X. Wang, Identity-based aggregate and verifiably encrypted signatures from bilinear pairing, in "Proceedings of ICCSA'05 (IV)" (eds. O. Gervasi et al.), Springer-Verlag, (2005), 1046-1054.
[27]	S. S. M. Chow, L. C. K. Hui, S. M Yiu and K. P. Chow, Two improved partially blind signature schemes from bilinear pairings, in "Proceedings of ACISP'05" (eds. C. Boyd and J.M. González Nieto), Springer-Verlag, (2005), 316-328.
[28]	I. Damgard, N. Fazio and A. Nicolosi, Non-interactive zero-knowledge from homomorphic encryption, in "Proceedings of TCC'06" (eds. S. Halevi and T. Rabin), Springer-Verlag, (2006), 41-59.
[29]	I. Damgard and T. P. Pedersen, New convertible undeniable signature schemes, in "Proceedings of Eurocrypt'96" (ed. U.M. Maurer), Springer-Verlag, (1996), 372-386.
[30]	Y. Dodis and J. Katz, Chosen-ciphertext security of multiple encryption, in "Proceedings of TCC'05" (ed. J. Kilian), Springer-Verlag, (2005), 188-209.
[31]	Y. Dodis, J. Katz, S. Xu and M. Yung, Key-insulated public key cryptosystems, in "Proceedings of Eurocrypt'02" (ed. L.R. Knudsen), Springer-Verlag, (2002), 65-82.
[32]	S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67.doi: 10.1007/BF02254791.
[33]	M. Fischlin, Round-optimal composable blind signatures in the common reference string model, in "Proceedings of Crypto'06" (ed. D. Dwork), Springer-Verlag, (2006), 60-77.
[34]	S. Galbraith and W. Mao, Invisibility and anonymity of undeniable and confirmer signatures, in "Proceedings of CT-RSA'03," (ed. M. Joye), Springer-Verlag, (2003), 80-97.
[35]	C. Gentry and Z. Ramzan, Identity-based aggregate signatures, in "Proceedings of PKC'06" (eds. M. Yung, Y. Dodis, A. Kiayias and T. Malkin), Springer-Verlag, (2006), 257-273.
[36]	C. Gentry and A. Silverberg, Hierarchical id-based cryptography, in "Proceedings of Asiacrypt'02" (ed. Y. Zheng), Springer-Verlag, (2002), 548-566.
[37]	S. Goldwasser, S. Micali and R. L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, 17 (1988), 281-308.doi: 10.1137/0217017.
[38]	S. Goldwasser and R. Ostrovsky, Invariant signatures and non-interactive zero-knowledge proofs are equivalent, in "Proceedings of Crypto'92" (ed. E.F. Brickell), Springer-Verlag, (1992), 228-245.
[39]	C. Gu and Y. Zhu, An id-based verifiable encrypted signature scheme based on Hess's scheme, in "Proceedings of CISC'05" (eds. D. Feng, D. Lin and M. Yung), Springer-Verlag, (2005), 42-52.
[40]	J. Herranz, Deterministic identity-based signatures for partial aggregation, The Computer Journal, 49 (2006), 322-330.doi: 10.1093/comjnl/bxh153.
[41]	B. C. Hu, D. S. Wong, Z. Zhang and X. Deng, Certificateless signature: a new security model and an improved generic construction, Designs, Codes and Cryptography, 42 (2007), 109-126.doi: 10.1007/s10623-006-9022-9.
[42]	M. Jakobsson, K. Sako and R. Impagliazzo, Designated verifier proofs and their applications, in "Proceedings of Eurocrypt'96" (ed. U.M. Maurer), Springer-Verlag, (1996), 143-154.
[43]	R. Johnson, D. Molnar, D. X. Song and D. Wagner, Homomorphic signature schemes, in "Proceedings of CT-RSA'02" (ed. B. Preneel), Springer-Verlag, (2002), 244-262.
[44]	A. Juels, M. Luby and R. Ostrovsky, Security of blind digital signatures, in "Proceedings of Crypto'97" (ed. B.S. Kaliski, Jr.), Springer-Verlag, (1997), 150-164.
[45]	E. Kiltz, A. Mityagin, S. Panjwani and B. Raghava, Append-only signatures, in "Proceedings of ICALP'05" (eds. L. Caires et al.), Springer-Verlag, (2005), 434-445.
[46]	H. Krawczyk, Simple forward-secure signatures from any signature scheme, in "Proceedings of CCS'00," ACM Press, (2000), 108-115.
[47]	H. Krawczyk and T. Rabin, Chameleon signatures, in "Proceedings of NDSS'00," The Internet Society, (2000).
[48]	F. Laguillaumie and D. Vergnaud, Short undeniable signatures without random oracles: the missing link, in "Proceedings of Indocrypt'05" (eds. S. Maitra, C.E.V. Madhavan and R. Venkatesan), Springer-Verlag, (2005), 283-296.
[49]	L. Lamport, Constructing digital signatures from a oneway function, Technical report, SRI International, (1979).
[50]	B. Libert and J-J. Quisquater, Identity based undeniable signatures, in "Proceedings of CT-RSA'04" (ed. T. Okamoto), Springer-Verlag, (2004), 112-125.
[51]	Y. Liu, X. Yin and L. Qiu, Id-based forward-secure signature scheme from the bilinear pairings, in "Proceedings of International Symposium on Electronic Commerce and Security," IEEE Computer Society, (2008), 179-183.doi: 10.1109/ISECS.2008.220.
[52]	S. Lu, R. Ostrovsky, A. Sahai, H. Shacham and B. Waters, Sequential aggregate signatures and multisignatures without random oracles, in "Proceedings of Eurocrypt'06" (ed. S. Vaudenay), Springer-Verlag, (2006), 465-485.
[53]	A. Lysyanskaya, Unique signatures and verifiable random functions from the dh-ddh separation, in "Proceedings of Crypto'02" (ed. M. Yung), Springer-Verlag, (2002), 597-612.
[54]	A. Lysyanskaya, S. Micali, L. Reyzin and H. Shacham, Sequential aggregate signatures from trapdoor permutations, in "Proceedings of Eurocrypt'04" (eds. C. Cachin and J. Camenisch), Springer-Verlag, (2004), 74-90.
[55]	M. Mambo, K. Usuda and E. Okamoto, Proxy signatures: delegation of the power to sign messages, IEICE Trans. Fundamentals, E79-A (1996), 1338-1353.
[56]	G. Neven, Efficient sequential aggregate signed data, in "Proceedings of Eurocrypt'08" (ed. N.P. Smart), Springer-Verlag, (2008), 52-69.
[57]	T. Okamoto, Efficient blind and partially blind signatures without random oracles, in "Proceedings of TCC'06" (eds. S. Halevi and T. Rabin), Springer-Verlag, (2006), 80-99.
[58]	L. T. Phong and W. Ogata, New identity-based blind signature and blind decryption scheme in the standard model, IEICE Trans. Fundamentals, E92-A (2009), 1822-1835.
[59]	D. Pointcheval and J. Stern, Security arguments for digital signatures and blind signatures, Journal of Cryptology, 13 (2000), 361-396.doi: 10.1007/s001450010003.
[60]	R. Rivest, A. Shamir and Y. Tauman, How to leak a secret, in "Proceedings of Asiacrypt'01" (ed. C. Boyd), Springer-Verlag, (2001), 552-565.
[61]	R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairings, in "Proceedings of Symposium on Cryptography and Information Security, SCIS 2000 (Japan)," (2000).
[62]	A. Shamir, Identity-based cryptosystems and signature schemes, in "Proceedings of Crypto'84" (eds. G.R. Blakley and D. Chaum), Springer-Verlag, (1985), 47-53.
[63]	A. Shamir and Y. Tauman, Improved online/offline signature schemes, in "Proceedings of Crypto'01" (ed. J. Kilian), Springer-Verlag, (2001), 355-367.
[64]	W. Susilo, F. Zhang and Y. Mu, Identity-based strong designated verifier signature schemes, in "Proceedings of ACISP'04" (eds. H. Wang, J. Pieprzyk and V. Varadharajan), Springer-Verlag, (2004), 313-324.
[65]	W. Susilo, F. Zhang and Y. Mu, On the security of nominative signatures, in "Proceedings of ACISP'05" (eds. C. Boyd and J.M. González Nieto), Springer-Verlag, (2005), 329-335.
[66]	G. Wang, W. Gao, X. Wang and F. Li, One-round id-based blind signature scheme without ROS assumption, in "Proceedings of Pairing'08" (eds. S.D. Galbraith and K.G. Paterson), Springer-Verlag, (2008), 316-331.
[67]	J. Weng, S. Liu, K. Chen and X. Li, Identity-based key-insulated signature with secure key-updates, in "Proceedings of Inscrypt'06" (eds. H. Lipmaa, M. Yung and D. Lin), Springer-Verlag, (2006), 13-26.
[68]	J. Xu, Z. Zhang and D. Feng, ID-based proxy signature using bilinear pairings, in "Proceedings of ISPA'05" (eds. G. Chen, Y. Pan, M. Guo and J. Lu), Springer-Verlag, (2005), 359-367.
[69]	S. Xu, Y. Mu and W. Susilo, Efficient authentication scheme for routing in mobile ad hoc networks, in "Proceedings of EUC Workshops'05" (eds. T. Enokido et al.), Springer-Verlag, (2005), 854-863.
[70]	F. Zhang and K. Kim, Id-based blind signature and ring signature from pairings, in "Proceedings of Asiacrypt'02" (ed. Y. Zheng), Springer-Verlag, (2002), 533-547.
[71]	F. Zhang and K. Kim, Efficient ID-based blind signature and proxy signature from bilinear pairings, in "Proceedings of ACISP'03" (eds. R. Safavi-Naini and J. Seberry), Springer-Verlag, (2003), 312-323.
[72]	Y. Zhou, Z. Cao and Z. Chai, Identity based key insulated signature, in "Proceedings of ISPEC'06" (eds. K. Chen, R.H. Deng, X. Lai and J. Zhou), Springer-Verlag, (2006), 226-234.