Abstract
We construct two efficient Identity-Based Encryption (IBE) systems that admit selective-identity security reductions without random oracles in groups equipped with a bilinear map. Selective-identity secure IBE is a slightly weaker security model than the standard security model for IBE. In this model the adversary must commit ahead of time to the identity that it intends to attack, whereas in an adaptive-identity attack the adversary is allowed to choose this identity adaptively. Our first system—BB1—is based on the well studied decisional bilinear Diffie–Hellman assumption, and extends naturally to systems with hierarchical identities, or HIBE. Our second system—BB2—is based on a stronger assumption which we call the Bilinear Diffie–Hellman Inversion assumption and provides another approach to building IBE systems.
Our first system, BB1, is very versatile and well suited for practical applications: the basic hierarchical construction can be efficiently secured against chosen-ciphertext attacks, and further extended to support efficient non-interactive threshold decryption, among others, all without using random oracles. Both systems, BB1 and BB2, can be modified generically to provide “full” IBE security (i.e., against adaptive-identity attacks), either using random oracles, or in the standard model at the expense of a non-polynomial but easy-to-compensate security reduction.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in Advances in Cryptology—EUROCRYPT 2010 (2010)
P.S.L.M. Barreto, M. Naehrig, Pairing-friendly elliptic curves of prime order, in Selected Areas in Cryptography—SAC 2005. LNCS, vol. 3897 (Springer, Berlin, 2005), pp. 319–331
M. Bellare, P. Rogaway, Random oracle are practical: A paradigm for designing efficient protocols, in Proceedings of the First ACM Conference on Computer and Communications Security (1993), pp. 62–73
E. Biham, D. Boneh, O. Reingold, Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring. Inf. Process. Lett. 70, 83–87 (1999)
I. Blake, G. Seroussi, N. Smart, Elliptic Curves in Cryptography. London Mathematical Society Lecture Note Series, vol. 265 (Cambridge University Press, Cambridge, 1999)
D. Boneh, X. Boyen, Efficient selective-ID identity based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 223–238
D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in Advances in Cryptology—CRYPTO 2004, ed. by Matt Franklin. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 443–459
D. Boneh, X. Boyen, Short signatures without random oracles, in Advances in Cryptology—EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 56–73
D. Boneh, X. Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)
D. Boneh, X. Boyen, S. Halevi, Chosen ciphertext secure public key threshold encryption without random oracles, in Topics in Cryptology—CT-RSA 2006. LNCS, vol. 3860 (Springer, Berlin, 2006), pp. 226–243
D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Advances in Cryptology—CRYPTO 2004. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 41–55
D. Boneh, R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. (SICOMP) 36(5), 915–942 (2006). Journal version of [23] and [16]
D. Boneh, M. Franklin, Identity-based encryption from the Weil pairing, in Advances in Cryptology—CRYPTO 2001, ed. by Joe Kilian. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 213–229
D. Boneh, M. Franklin, Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
D. Boneh, C. Gentry, M. Hamburg, Space-efficient identity based encryption without pairings, in Proceedings of FOCS 2007 (2007), pp. 647–657
D. Boneh, J. Katz, Improved efficiency for CCA-secure cryptosystems built using identity based encryption, in Proceedings of CT-RSA 2005. LNCS, vol. 3376 (Springer, Berlin, 2005)
D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing, in Advances in Cryptology—ASIACRYPT 2001. LNCS, vol. 2248 (Springer, Berlin, 2001), pp. 514–532
D. Boneh, A. Silverberg, Applications of multilinear forms to cryptography. Contemp. Math. 324, 71–90 (2003)
X. Boyen, General ad hoc encryption from exponent inversion IBE, in Advances in Cryptology—EUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 394–411
X. Boyen, Q. Mei, B. Waters, Direct chosen ciphertext security from identity-based techniques, in ACM Conference on Computer and Communications Security—CCS 2005 (ACM, New York, 2005)
D. Brown, R. Gallant, The static Diffie–Hellman problem. Cryptology ePrint Archive, Report 2004/306 (2004). http://eprint.iacr.org/
R. Canetti, S. Halevi, J. Katz, A forward-secure public-key encryption scheme, in Advances in Cryptology—EUROCRYPT 2003. LNCS, vol. 2656 (Springer, Berlin, 2003)
R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption, in Advances in Cryptology—EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 207–222
D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, Bonsai trees, or how to delegate a lattice basis, in Advances in Cryptology—EUROCRYPT 2010 (2010)
L. Chen, Z. Cheng, Security proof of Sakai-Kasahara’s identity-based encryption scheme, in Cryptography and Coding, 10th IMA International Conference (2005), pp. 442–459
J.H. Cheon, Security analysis of the strong Diffie–Hellman problem, in Advances in Cryptology—EUROCRYPT 2006. LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 1–11
C. Chevalier, P.-A. Fouque, D. Pointcheval, S. Zimmer, Optimal randomness extraction from a Diffie–Hellman element, in Advances in Cryptology—EUROCRYPT 2009 (2009), pp. 572–589
C. Cocks, An identity based encryption scheme based on quadratic residues, in Proceedings of the 8th IMA International Conference on Cryptography and Coding (2001), pp. 26–28
R. Cramer, V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attacks, in Advances in Cryptology—CRYPTO 1998, ed. by H. Krawczyk. LNCS, vol. 1462 (Springer, Berlin, 1998), pp. 13–25
G. Di Crescenzo, V. Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in Proceedings of INDOCRYPT 2007 (2007), pp. 282–296
D. Freeman, Constructing pairing-friendly elliptic curves with embedding degree 10, in Proceedings of ANTS 2006 (2006), pp. 452–465
D. Freeman, M. Scott, E. Teske, A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006). http://eprint.iacr.org/
E. Fujisaki, T. Okamoto, Secure integration of asymmetric and symmetric encryption schemes, in Advances in Cryptology—CRYPTO 1999. LNCS (Springer, Berlin, 1999), pp. 537–554
E. Fujisaki, T. Okamoto, How to enhance the security of public-key encryption at minimum cost. IEICE Trans. Fundam. E83-9(1), 24–32 (2000)
S. Galbraith, K. Paterson, N. Smart, Pairings for cryptographers. Discrete Appl. Math. 156(16), 3113–3121 (2008)
D. Galindo, A separation between selective and full-identity security notions for identity-based encryption. ICCSA 3, 318–326 (2006)
C. Gentry, Practical identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2006. LNCS (Springer, Berlin, 2006)
C. Gentry, S. Halevi, Hierarchical identity based encryption with polynomially many levels, in Theory of Cryptography—TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 437–456
C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in Proceedings of STOC 2008 (2008), pp. 197–206
C. Gentry, A. Silverberg, Hierarchical ID-based cryptography, in Advances in Cryptology—ASIACRYPT 2002. LNCS (Springer, Berlin, 2002)
S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
J. Horwitz, B. Lynn, Towards hierarchical identity-based encryption, in Advances in Cryptology—EUROCRYPT 2002. LNCS (Springer, Berlin, 2002), pp. 466–481
R. Impagliazzo, L. Levin, M. Luby, Pseudo random generation from one-way functions, in Proceedings of the 21st ACM Symposium on Theory of Computing (1989)
A. Joux, A one round protocol for tripartite Diffie–Hellman, in Proceedings of ANTS IV, ed. by W. Bosma. LNCS, vol. 1838 (Springer, Berlin, 2000), pp. 385–394
E. Kiltz, From selective-ID to full security: The case of the inversion-based Boneh-Boyen IBE scheme. Cryptology ePrint Archive, Report 2007/033 (2007). http://eprint.iacr.org/
K. Kurosawa, Y. Desmedt, A new paradigm of hybrid encryption scheme, in Advances in Cryptology—CRYPTO 2004. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 426–442
Y. Lindell, A simpler construction of CCA2-secure public-key encryption under general assumptions, in Advances in Cryptology—EUROCRYPT 2003. LNCS, vol. 2656 (Springer, Berlin, 2003), pp. 241–254
A. Lysyanskaya, Unique signatures and verifiable random functions from the DH-DDH separation, in Advances in Cryptology—CRYPTO 2002. LNCS (Springer, Berlin, 2002)
U.M. Maurer, Y. Yacobi, A non-interactive public-key distribution system. Des. Codes Cryptogr. 9(3), 305–316 (1996)
V. Miller, The Weil pairing, and its efficient calculation. J. Cryptol. 17(4), 235–261 (2004)
S. Mitsunari, R. Sakai, M. Kasahara, A new traitor tracing. IEICE Trans. Fundam. E85-A(2), 481–484 (2002)
A. Miyaji, M. Nakabayashi, S. Takano, New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. E84-A(5), 1234–1243 (2001)
M. Naor, O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, in Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (1997), pp. 458–467
M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in Proceedings of the 21st ACM Symposium on Theory of Computing (ACM, New York, 1989)
M. Naor, M. Yung, Public key cryptosystems provable secure against chosen ciphertext attacks, in Proceedings of the 22nd ACM Symposium on Theory of Computing (ACM, New York, 1990), pp. 427–437
K. Rubin, A. Silverberg, Supersingular Abelian varieties in cryptology, in Advances in Cryptology—CRYPTO 2002 (2002), pp. 336–353
A. Sahai, Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security, in Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999)
R. Sakai, M. Kasahara, ID based cryptosystems with pairing over elliptic curve. Cryptology ePrint Archive, Report 2003/054 (2003). http://eprint.iacr.org/
R. Sakai, K. Ohgishi, M. Kasahara, Cryptosystems based on pairings, in Proceedings of the Symposium on Cryptography and Information Security—SCIS 2000, Japan, 2000
M. Scott, Computing the Tate pairing, in Proceedings of CT-RSA 2005. LNCS, vol. 3376 (Springer, Berlin, 2005), pp. 293–304
A. Shamir, Identity-based cryptosystems and signature schemes, in Advances in Cryptology—CRYPTO 1984. LNCS, vol. 196 (Springer, Berlin, 1984), pp. 47–53
E. Shen, Making the BB2-IBE scheme fully secure. Unpublished note (2006)
E. Shi, B. Waters, Delegating capabilities in predicate encryption systems, in ICALP (2008), pp. 560–578
V. Shoup, Lower bounds for discrete logarithms and related problems, in Advances in Cryptology—EUROCRYPT 1997. LNCS, vol. 1233 (Springer, Berlin, 1997), pp. 256–266
V. Shoup, R. Gennaro, Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptol. 15(2), 75–96 (2002). Extended abstract in Eurocrypt ’98
M. Steiner, G. Tsudik, M. Waidner, Diffie-Hellman key distribution extended to groups, in Proceedings of the ACM Conference on Computer and Communications Security (1996)
H. Tanaka, A realization scheme for the identity-based cryptosystem, in Advances in Cryptology—CRYPTO 1987. LNCS, vol. 293 (Springer, Berlin, 1987), pp. 341–349
S. Tsujii, T. Itoh, An ID-based cryptosystem based on the discrete logarithm problem. IEEE J. Sel. Areas Commun. 7(4), 467–473 (1989)
B. Waters, Efficient identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2005. LNCS, vol. 3494 (Springer, Berlin, 2005)
B. Waters, Dual key encryption: Realizing fully secure IBE and HIBE under simple assumption, in Advances in Cryptology—CRYPTO 2009 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Matthew Franklin
An extended abstract entitled “Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles” appears in Eurocrypt 2004 [6].
Rights and permissions
About this article
Cite this article
Boneh, D., Boyen, X. Efficient Selective Identity-Based Encryption Without Random Oracles. J Cryptol 24, 659–693 (2011). https://doi.org/10.1007/s00145-010-9078-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9078-6