{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T18:06:27Z","timestamp":1793124387929,"version":"4.5.0"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T00:00:00Z","timestamp":1315267200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00145-011-9105-2","type":"journal-article","created":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T12:36:07Z","timestamp":1315312567000},"page":"601-639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":208,"title":["Bonsai Trees, or How to Delegate a Lattice Basis"],"prefix":"10.1007","volume":"25","author":[{"given":"David","family":"Cash","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Hofheinz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eike","family":"Kiltz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,9,6]]},"reference":[{"issue":"3","key":"9105_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/s00145-007-9006-6","volume":"21","author":"M. Abdalla","year":"2008","unstructured":"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\u2013391 (2008). Preliminary version in CRYPTO 2005","journal-title":"J. Cryptol."},{"key":"9105_CR2","unstructured":"S. Agrawal, X. Boyen, Identity-based encryption from lattices in the standard model. Manuscript. July 2009"},{"key":"9105_CR3","first-page":"553","volume-title":"EUROCRYPT","author":"S. Agrawal","year":"2010","unstructured":"S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in EUROCRYPT (2010), pp. 553\u2013572"},{"key":"9105_CR4","first-page":"1","volume-title":"ICALP","author":"M. Ajtai","year":"1999","unstructured":"M. Ajtai, Generating hard instances of the short basis problem, in ICALP (1999), pp. 1\u20139"},{"key":"9105_CR5","first-page":"1","volume":"13","author":"M. Ajtai","year":"2004","unstructured":"M. Ajtai, Generating hard instances of lattice problems. Quad. Mat. 13, 1\u201332 (2004). Preliminary version in STOC 1996","journal-title":"Quad. Mat."},{"key":"9105_CR6","first-page":"75","volume-title":"STACS","author":"J. Alwen","year":"2009","unstructured":"J. Alwen, C. Peikert, Generating shorter bases for hard random lattices, in STACS (2009), pp. 75\u201386"},{"key":"9105_CR7","first-page":"566","volume-title":"ASIACRYPT","author":"M. Bellare","year":"2001","unstructured":"M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval, Key-privacy in public-key encryption, in ASIACRYPT (2001), pp. 566\u2013582"},{"key":"9105_CR8","first-page":"223","volume-title":"EUROCRYPT","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in EUROCRYPT (2004), pp.\u00a0223\u2013238"},{"key":"9105_CR9","first-page":"443","volume-title":"CRYPTO","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in CRYPTO (2004), pp.\u00a0443\u2013459"},{"issue":"3","key":"9105_CR10","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/S0097539701398521","volume":"32","author":"D. Boneh","year":"2003","unstructured":"D. Boneh, M.K. Franklin, Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586\u2013615 (2003). Preliminary version in CRYPTO 2001","journal-title":"SIAM J. Comput."},{"key":"9105_CR11","first-page":"506","volume-title":"EUROCRYPT","author":"D. Boneh","year":"2004","unstructured":"D. Boneh, G.D. Crescenzo, R. Ostrovsky, G. Persiano, Public key encryption with keyword search, in EUROCRYPT (2004), pp. 506\u2013522"},{"issue":"5","key":"9105_CR12","doi-asserted-by":"publisher","first-page":"1301","DOI":"10.1137\/S009753970544713X","volume":"36","author":"D. Boneh","year":"2007","unstructured":"D. Boneh, R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301\u20131328 (2007)","journal-title":"SIAM J. Comput."},{"key":"9105_CR13","first-page":"647","volume-title":"FOCS","author":"D. Boneh","year":"2007","unstructured":"D. Boneh, C. Gentry, M. Hamburg, Space-efficient identity based encryption without pairings, in FOCS (2007), pp. 647\u2013657"},{"key":"9105_CR14","first-page":"499","volume-title":"Public Key Cryptography","author":"X. Boyen","year":"2010","unstructured":"X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in Public Key Cryptography (2010), pp. 499\u2013517"},{"key":"9105_CR15","first-page":"290","volume-title":"CRYPTO","author":"X. Boyen","year":"2006","unstructured":"X. Boyen, B. Waters, Anonymous hierarchical identity-based encryption (without random oracles), in CRYPTO (2006), pp. 290\u2013307"},{"issue":"3","key":"9105_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s00145-006-0442-5","volume":"20","author":"R. Canetti","year":"2007","unstructured":"R. Canetti, S. Halevi, J. Katz, A forward-secure public-key encryption scheme. J. Cryptol. 20(3), 265\u2013294 (2007) Preliminary version in EUROCRYPT 2003","journal-title":"J. Cryptol."},{"key":"9105_CR17","unstructured":"D. Cash, D. Hofheinz, E. Kiltz, How to delegate a lattice basis. Cryptology ePrint Archive, Report 2009\/351, July 2009. http:\/\/eprint.iacr.org\/"},{"key":"9105_CR18","first-page":"360","volume-title":"IMA Int. Conf","author":"C. Cocks","year":"2001","unstructured":"C. Cocks, An identity based encryption scheme based on quadratic residues, in IMA Int. Conf (2001), pp. 360\u2013363"},{"key":"9105_CR19","first-page":"282","volume-title":"INDOCRYPT","author":"G.D. Crescenzo","year":"2007","unstructured":"G.D. Crescenzo, V. Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in INDOCRYPT (2007), pp. 282\u2013296"},{"key":"9105_CR20","first-page":"61","volume-title":"ACM Workshop on Digital Rights Management","author":"Y. Dodis","year":"2002","unstructured":"Y. Dodis, N. Fazio, Public key broadcast encryption for stateless receivers, in ACM Workshop on Digital Rights Management (2002), pp. 61\u201380"},{"key":"9105_CR21","first-page":"445","volume-title":"EUROCRYPT","author":"C. Gentry","year":"2006","unstructured":"C. Gentry, Practical identity-based encryption without random oracles, in EUROCRYPT (2006), pp. 445\u2013464"},{"key":"9105_CR22","first-page":"437","volume-title":"TCC","author":"C. Gentry","year":"2009","unstructured":"C. Gentry, S. Halevi, Hierarchical identity based encryption with polynomially many levels, in TCC (2009), pp. 437\u2013456"},{"key":"9105_CR23","first-page":"548","volume-title":"ASIACRYPT","author":"C. Gentry","year":"2002","unstructured":"C. Gentry, A. Silverberg, Hierarchical ID-based cryptography, in ASIACRYPT (2002), pp. 548\u2013566"},{"key":"9105_CR24","first-page":"197","volume-title":"STOC","author":"C. Gentry","year":"2008","unstructured":"C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC (2008), pp. 197\u2013206"},{"key":"9105_CR25","first-page":"112","volume-title":"CRYPTO","author":"O. Goldreich","year":"1997","unstructured":"O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, in CRYPTO (1997), pp. 112\u2013131"},{"issue":"2","key":"9105_CR26","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S. Goldwasser","year":"1988","unstructured":"S. Goldwasser, S. Micali, R.L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281\u2013308 (1988). Preliminary version in FOCS 1984","journal-title":"SIAM J. Comput."},{"key":"9105_CR27","first-page":"267","volume-title":"ANTS","author":"J. Hoffstein","year":"1998","unstructured":"J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: a ring-based public key cryptosystem, in ANTS (1998), pp. 267\u2013288"},{"key":"9105_CR28","first-page":"122","volume-title":"CT-RSA","author":"J. Hoffstein","year":"2003","unstructured":"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\u2013140"},{"key":"9105_CR29","first-page":"654","volume-title":"CRYPTO","author":"S. Hohenberger","year":"2009","unstructured":"S. Hohenberger, B. Waters, Short and stateless signatures from the RSA assumption, in CRYPTO (2009), pp. 654\u2013670"},{"key":"9105_CR30","first-page":"466","volume-title":"EUROCRYPT","author":"J. Horwitz","year":"2002","unstructured":"J. Horwitz, B. Lynn, Toward hierarchical identity-based encryption, in EUROCRYPT (2002), pp. 466\u2013481"},{"key":"9105_CR31","volume-title":"NDSS","author":"H. Krawczyk","year":"2000","unstructured":"H. Krawczyk, T. Rabin, Chameleon signatures, in NDSS (2000)"},{"key":"9105_CR32","first-page":"445","volume-title":"CRYPTO","author":"G. Leurent","year":"2009","unstructured":"G. Leurent, P.Q. Nguyen, How risky is the random-oracle model, in CRYPTO (2009), pp. 445\u2013464"},{"key":"9105_CR33","first-page":"144","volume-title":"ICALP (2)","author":"V. Lyubashevsky","year":"2006","unstructured":"V. Lyubashevsky, D. Micciancio, Generalized compact knapsacks are collision resistant, in ICALP (2) (2006), pp. 144\u2013155"},{"key":"9105_CR34","first-page":"37","volume-title":"TCC","author":"V. Lyubashevsky","year":"2008","unstructured":"V. Lyubashevsky, D. Micciancio, Asymptotically efficient lattice-based digital signatures, in TCC (2008), pp. 37\u201354"},{"key":"9105_CR35","first-page":"1","volume-title":"EUROCRYPT","author":"V. Lyubashevsky","year":"2010","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in EUROCRYPT (2010), pp. 1\u201323"},{"issue":"4","key":"9105_CR36","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00037-007-0234-9","volume":"16","author":"D. Micciancio","year":"2007","unstructured":"D. Micciancio, Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4), 365\u2013411 (2007). Preliminary version in FOCS 2002","journal-title":"Comput. Complex."},{"key":"9105_CR37","series-title":"The Kluwer International Series in Engineering and Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"D. Micciancio","year":"2002","unstructured":"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)"},{"issue":"1","key":"9105_CR38","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D. Micciancio","year":"2007","unstructured":"D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267\u2013302 (2007). Preliminary version in FOCS 2004","journal-title":"SIAM J. Comput."},{"key":"9105_CR39","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/384101.384133","volume-title":"ISSAC","author":"D. Micciancio","year":"2001","unstructured":"D. Micciancio, B. Warinschi, A linear space algorithm for computing the Hermite normal form, in ISSAC (2001), pp. 231\u2013236"},{"key":"9105_CR40","first-page":"33","volume-title":"STOC","author":"M. Naor","year":"1989","unstructured":"M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC (1989), pp. 33\u201343"},{"key":"9105_CR41","first-page":"333","volume-title":"STOC","author":"C. Peikert","year":"2009","unstructured":"C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in STOC (2009), pp. 333\u2013342"},{"key":"9105_CR42","unstructured":"C. Peikert, Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive, Report 2009\/359, July 2009. http:\/\/eprint.iacr.org\/"},{"key":"9105_CR43","first-page":"80","volume-title":"CRYPTO","author":"C. Peikert","year":"2010","unstructured":"C. Peikert, An efficient and parallel Gaussian sampler for lattices, in CRYPTO (2010), pp. 80\u201397"},{"key":"9105_CR44","first-page":"145","volume-title":"TCC","author":"C. Peikert","year":"2006","unstructured":"C. Peikert, A. Rosen, Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, in TCC (2006), pp. 145\u2013166"},{"key":"9105_CR45","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1145\/1250790.1250860","volume-title":"STOC","author":"C. Peikert","year":"2007","unstructured":"C. Peikert, A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in STOC (2007), pp. 478\u2013487"},{"key":"9105_CR46","first-page":"554","volume-title":"CRYPTO","author":"C. Peikert","year":"2008","unstructured":"C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO (2008), pp. 554\u2013571"},{"key":"9105_CR47","unstructured":"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)"},{"issue":"6","key":"9105_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O. Regev","year":"2009","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1\u201340 (2009). Preliminary version in STOC 2005","journal-title":"J. ACM"},{"key":"9105_CR49","first-page":"182","volume-title":"PQCrypto","author":"M. R\u00fcckert","year":"2010","unstructured":"M. R\u00fcckert, Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles, in PQCrypto (2010), pp. 182\u2013200"},{"key":"9105_CR50","first-page":"47","volume-title":"CRYPTO","author":"A. Shamir","year":"1984","unstructured":"A. Shamir, Identity-based cryptosystems and signature schemes, in CRYPTO (1984), pp. 47\u201353"},{"key":"9105_CR51","first-page":"355","volume-title":"CRYPTO","author":"A. Shamir","year":"2001","unstructured":"A. Shamir, Y. Tauman, Improved online\/offline signature schemes, in CRYPTO (2001), pp. 355\u2013367"},{"key":"9105_CR52","first-page":"617","volume-title":"ASIACRYPT","author":"D. Stehl\u00e9","year":"2009","unstructured":"D. Stehl\u00e9, R. Steinfeld, K. Tanaka, K. Xagawa, Efficient public key encryption based on ideal lattices, in ASIACRYPT (2009), pp. 617\u2013635"},{"key":"9105_CR53","first-page":"114","volume-title":"EUROCRYPT","author":"B. Waters","year":"2005","unstructured":"B. Waters, Efficient identity-based encryption without random oracles, in EUROCRYPT (2005), pp. 114\u2013127"},{"key":"9105_CR54","first-page":"619","volume-title":"CRYPTO","author":"B. Waters","year":"2009","unstructured":"B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in CRYPTO (2009), pp. 619\u2013636"},{"key":"9105_CR55","first-page":"354","volume-title":"ACM Conference on Computer and Communications Security","author":"D. Yao","year":"2004","unstructured":"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\u2013363"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9105-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-011-9105-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9105-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-011-9105-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T02:39:43Z","timestamp":1686278383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-011-9105-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,6]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9105"],"URL":"https:\/\/doi.org\/10.1007\/s00145-011-9105-2","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,6]]},"assertion":[{"value":"2 November 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2011","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}