Abstract
In this paper, we introduce a new primitive called identity-based encryption with wildcards, or WIBE for short. It allows a sender to encrypt messages to a whole range of receivers whose identities match a certain pattern. This pattern is defined through a sequence of fixed strings and wildcards, where any string can take the place of a wildcard in a matching identity. Our primitive can be applied to provide an intuitive way to send encrypted email to groups of users in a corporate hierarchy. We propose a full security notion and give efficient implementations meeting this notion under different pairing-related assumptions, both in the random oracle model and in the standard model.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abdalla, D. Catalano, A. Dent, J. Malone-Lee, G. Neven, N. Smart, Identity-based encryption gone wild, in ICALP 2006: 33rd International Colloquium on Automata, Languages and Programming, Part II, Venice, Italy, July 10–14, 2006, ed. by M. Bugliesi, B. Preneel, V. Sassone, I. Wegener. Lecture Notes in Computer Science, vol. 4052 (Springer, Berlin, 2006), pp. 300–311
M. Bellare, P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in ACM CCS 93: 1st Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3–5, 1993, ed. by V. Ashby (ACM Press, New York, 1993), pp. 62–73
K. Bentahar, P. Farshim, J. Malone-Lee, N.P. Smart, Generic constructions of identity-based and certificateless KEMs. J. Cryptol. 21(2), 178–199 (2008)
J. Bethencourt, A. Sahai, B. Waters, Ciphertext-policy attribute-based encryption, in 2007 IEEE Symposium on Security and Privacy, Oakland, California, USA, May 20–23, 2007 (IEEE Computer Society Press, Los Alamitos, 2007), pp. 321–334
J. Birkett, A.W. Dent, G. Neven, J.C.N. Schuldt, Efficient chosen-ciphertext secure identity-based encryption with wildcards, in ACISP 07: 12th Australasian Conference on Information Security and Privacy, Townsville, Australia, July 2–4, 2007, ed. by J. Pieprzyk, H. Ghodosi, E. Dawson. Lecture Notes in Computer Science, vol. 4586 (Springer, Berlin, 2007), pp. 274–292
M. Blum, S. Goldwasser, An efficient probabilistic public-key encryption scheme which hides all partial information, in Advances in Cryptology—CRYPTO’84, Santa Barbara, CA, USA, August 19–23, 1985, ed. by G.R. Blakley, D. Chaum. Lecture Notes in Computer Science, vol. 196 (Springer, Berlin, 1985), pp. 289–302
D. Boneh, X. Boyen, Efficient selective-ID secure identity based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2004, Interlaken, Switzerland, May 2–6, 2004, ed. by C. Cachin, J. Camenisch. Lecture Notes in Computer Science, vol. 3027 (Springer, Berlin, 2004), pp. 223–238
D. Boneh, M.K. Franklin, Identity based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
D. Boneh, M. Hamburg, Generalized identity based and broadcast encryption schemes, in Advances in Cryptology—ASIACRYPT 2008, Melbourne, Australia, December 7–11, 2008, ed. by J. Pieprzyk. Lecture Notes in Computer Science, vol. 5350 (Springer, Berlin, 2008), pp. 455–470
D. Boneh, X. Boyen, E.-J. Goh, Hierarchical identity based encryption with constant size ciphertext, in Advances in Cryptology—EUROCRYPT 2005, Aarhus, Denmark, May 22–26, 2005, ed. by R. Cramer. Lecture Notes in Computer Science, vol. 3494 (Springer, Berlin, 2005), pp. 440–456
R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption, in Advances in Cryptology—EUROCRYPT 2004, Interlaken, Switzerland, May 2–6, 2004, ed. by C. Cachin, J. Camenisch. Lecture Notes in Computer Science, vol. 3027 (Springer, Berlin, 2004), pp. 207–222
S. Chatterjee, P. Sarkar, Trading time for space: Towards an efficient IBE scheme with short(er) public parameters in the standard model, in ICISC: 8th International Conference on Information Security and Cryptology, Seoul, Korea, December 1–2, 2005, ed. by D. Won, S. Kim. Lecture Notes in Computer Science, vol. 3935 (Springer, Berlin, 2005), pp. 424–440
C. Cocks, An identity based encryption scheme based on quadratic residues, in Cryptography and Coding, 8th IMA International Conference, Cirencester, UK, December 17–19, 2001, ed. by B. Honary. Lecture Notes in Computer Science, vol. 2260 (Springer, Berlin, 2001), pp. 360–363
R. Cramer, V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)
A.W. Dent, A designer’s guide to KEMs, in Cryptography and Coding, 9th IMA International Conference, Cirencester, UK, 2003, ed. by K.G. Paterson. Lecture Notes in Computer Science, vol. 2898 (Springer, Berlin, 2003), pp. 133–151
C. Gentry, A. Silverberg, Hierarchical ID-based cryptography, in Advances in Cryptology—ASIACRYPT 2002, Queenstown, New Zealand, December 1–5, 2002, ed. by Y. Zheng. Lecture Notes in Computer Science, vol. 2501 (Springer, Berlin, 2002), pp. 548–566
V. Goyal, O. Pandey, A. Sahai, B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, in ACM CCS 06: 13th Conference on Computer and Communications Security, Alexandria, Virginia, USA, October 30–November 3, 2006, ed. by A. Juels, R.N. Wright, S. De Capitani di Vimercati (ACM Press, New York, 2006), pp. 89–98. Available as Cryptology ePrint Archive Report 2006/309
J. Horwitz, B. Lynn, Toward hierarchical identity-based encryption, in Advances in Cryptology—EUROCRYPT 2002, Amsterdam, The Netherlands, April 28 – May 2, 2002, ed. by L.R. Knudsen. Lecture Notes in Computer Science, vol. 2332 (Springer, Berlin, 2002), pp. 466–481
A. Joux, A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17(4), 263–276 (2004).
E. Kiltz, D. Galindom, Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. Theor. Comput. Sci. 410(47–49), 5093–5111 (2009)
S. Mitsunari, R. Saka, M. Kasahara, A new traitor tracing. IEICE Trans. E85-A(2), 481–484 (2002)
D. Naccache, Secure and practical identity-based encryption. IET Inf. Secur. 1(2), 59–64 (2007)
A. Sahai, B.R. Waters, Fuzzy identity-based encryption, in Advances in Cryptology—EUROCRYPT 2005, Aarhus, Denmark, May 22–26, 2005, ed. by R. Cramer. Lecture Notes in Computer Science, vol. 3494 (Springer, Berlin, 2005), pp. 457–473
R. Sakai, K. Ohgishi, M. Kasahara, Cryptosystems based on pairing, in SCIS 2000, Okinawa, Japan, January 2000
A. Shamir, Identity-based cryptosystems and signature schemes, in Advances in Cryptology—CRYPTO’84, Santa Barbara, CA, USA, August 19–23, 1985, ed. by G.R. Blakley, D. Chaum. Lecture Notes in Computer Science, vol. 196 (Springer, Berlin, 1985), pp. 47–53
N.P. Smart, Access control using pairing based cryptography, in Topics in Cryptology—CT-RSA 2003, San Francisco, CA, USA, April 13–17, 2003, ed. by M. Joye. Lecture Notes in Computer Science, vol. 2612 (Springer, Berlin, 2003), pp. 111–121
B.R. Waters, Efficient identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2005, Aarhus, Denmark, May 22–26, 2005, ed. by R. Cramer. Lecture Notes in Computer Science, vol. 3494 (Springer, Berlin, 2005), pp. 114–127
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Abdalla, M., Birkett, J., Catalano, D. et al. Wildcarded Identity-Based Encryption. J Cryptol 24, 42–82 (2011). https://doi.org/10.1007/s00145-010-9060-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9060-3