Abstract
We introduce a new lattice-based cryptographic structure called a bonsai tree, and use it to resolve some important open problems in the area. Applications of bonsai trees include an efficient, stateless ‘hash-and-sign’ signature scheme in the standard model (i.e., no random oracles), and the first hierarchical identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, H. Shi, Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions. J. Cryptol. 21(3), 350–391 (2008). Preliminary version in CRYPTO 2005
S. Agrawal, X. Boyen, Identity-based encryption from lattices in the standard model. Manuscript. July 2009
S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in EUROCRYPT (2010), pp. 553–572
M. Ajtai, Generating hard instances of the short basis problem, in ICALP (1999), pp. 1–9
M. Ajtai, Generating hard instances of lattice problems. Quad. Mat. 13, 1–32 (2004). Preliminary version in STOC 1996
J. Alwen, C. Peikert, Generating shorter bases for hard random lattices, in STACS (2009), pp. 75–86
M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval, Key-privacy in public-key encryption, in ASIACRYPT (2001), pp. 566–582
D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in EUROCRYPT (2004), pp. 223–238
D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in CRYPTO (2004), pp. 443–459
D. Boneh, M.K. Franklin, Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003). Preliminary version in CRYPTO 2001
D. Boneh, G.D. Crescenzo, R. Ostrovsky, G. Persiano, Public key encryption with keyword search, in EUROCRYPT (2004), pp. 506–522
D. Boneh, R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2007)
D. Boneh, C. Gentry, M. Hamburg, Space-efficient identity based encryption without pairings, in FOCS (2007), pp. 647–657
X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in Public Key Cryptography (2010), pp. 499–517
X. Boyen, B. Waters, Anonymous hierarchical identity-based encryption (without random oracles), in CRYPTO (2006), pp. 290–307
R. Canetti, S. Halevi, J. Katz, A forward-secure public-key encryption scheme. J. Cryptol. 20(3), 265–294 (2007) Preliminary version in EUROCRYPT 2003
D. Cash, D. Hofheinz, E. Kiltz, How to delegate a lattice basis. Cryptology ePrint Archive, Report 2009/351, July 2009. http://eprint.iacr.org/
C. Cocks, An identity based encryption scheme based on quadratic residues, in IMA Int. Conf (2001), pp. 360–363
G.D. Crescenzo, V. Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in INDOCRYPT (2007), pp. 282–296
Y. Dodis, N. Fazio, Public key broadcast encryption for stateless receivers, in ACM Workshop on Digital Rights Management (2002), pp. 61–80
C. Gentry, Practical identity-based encryption without random oracles, in EUROCRYPT (2006), pp. 445–464
C. Gentry, S. Halevi, Hierarchical identity based encryption with polynomially many levels, in TCC (2009), pp. 437–456
C. Gentry, A. Silverberg, Hierarchical ID-based cryptography, in ASIACRYPT (2002), pp. 548–566
C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC (2008), pp. 197–206
O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, in CRYPTO (1997), pp. 112–131
S. Goldwasser, S. Micali, R.L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988). Preliminary version in FOCS 1984
J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: a ring-based public key cryptosystem, in ANTS (1998), pp. 267–288
J. Hoffstein, N. Howgrave-Graham, J. Pipher, J.H. Silverman, W. Whyte, NTRUSIGN: digital signatures using the NTRU lattice, in CT-RSA (2003), pp. 122–140
S. Hohenberger, B. Waters, Short and stateless signatures from the RSA assumption, in CRYPTO (2009), pp. 654–670
J. Horwitz, B. Lynn, Toward hierarchical identity-based encryption, in EUROCRYPT (2002), pp. 466–481
H. Krawczyk, T. Rabin, Chameleon signatures, in NDSS (2000)
G. Leurent, P.Q. Nguyen, How risky is the random-oracle model, in CRYPTO (2009), pp. 445–464
V. Lyubashevsky, D. Micciancio, Generalized compact knapsacks are collision resistant, in ICALP (2) (2006), pp. 144–155
V. Lyubashevsky, D. Micciancio, Asymptotically efficient lattice-based digital signatures, in TCC (2008), pp. 37–54
V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in EUROCRYPT (2010), pp. 1–23
D. Micciancio, Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4), 365–411 (2007). Preliminary version in FOCS 2002
D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671 (Kluwer Academic, Dordrecht, 2002)
D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). Preliminary version in FOCS 2004
D. Micciancio, B. Warinschi, A linear space algorithm for computing the Hermite normal form, in ISSAC (2001), pp. 231–236
M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC (1989), pp. 33–43
C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in STOC (2009), pp. 333–342
C. Peikert, Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive, Report 2009/359, July 2009. http://eprint.iacr.org/
C. Peikert, An efficient and parallel Gaussian sampler for lattices, in CRYPTO (2010), pp. 80–97
C. Peikert, A. Rosen, Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, in TCC (2006), pp. 145–166
C. Peikert, A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in STOC (2007), pp. 478–487
C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO (2008), pp. 554–571
M.O. Rabin, Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science (1979)
O. Regev, On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009). Preliminary version in STOC 2005
M. Rückert, Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles, in PQCrypto (2010), pp. 182–200
A. Shamir, Identity-based cryptosystems and signature schemes, in CRYPTO (1984), pp. 47–53
A. Shamir, Y. Tauman, Improved online/offline signature schemes, in CRYPTO (2001), pp. 355–367
D. Stehlé, R. Steinfeld, K. Tanaka, K. Xagawa, Efficient public key encryption based on ideal lattices, in ASIACRYPT (2009), pp. 617–635
B. Waters, Efficient identity-based encryption without random oracles, in EUROCRYPT (2005), pp. 114–127
B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in CRYPTO (2009), pp. 619–636
D. Yao, N. Fazio, Y. Dodis, A. Lysyanskaya, ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption, in ACM Conference on Computer and Communications Security (2004), pp. 354–363
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ivan Damgard
This paper was solicited from Eurocrypt 2010.
Part of this work was performed while D. Cash was at Georgia Institute of Technology.
Part of this work was performed while D. Hofheinz was at CWI.
Rights and permissions
About this article
Cite this article
Cash, D., Hofheinz, D., Kiltz, E. et al. Bonsai Trees, or How to Delegate a Lattice Basis. J Cryptol 25, 601–639 (2012). https://doi.org/10.1007/s00145-011-9105-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-011-9105-2