More Web Proxy on the site http://driver.im/

article

Bonsai Trees, or How to Delegate a Lattice Basis

Authors:

Dennis Hofheinz,

Chris PeikertAuthors Info & Claims

Journal of Cryptology, Volume 25, Issue 4

Pages 601 - 639

https://doi.org/10.1007/s00145-011-9105-2

Published: 01 October 2012 Publication History

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.

References

[1]

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.

Digital Library

[2]

S. Agrawal, X. Boyen, Identity-based encryption from lattices in the standard model. Manuscript. July 2009.

[3]

S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in EUROCRYPT (2010), pp. 553-572.

[4]

M. Ajtai, Generating hard instances of the short basis problem, in ICALP (1999), pp. 1-9.

Digital Library

[5]

M. Ajtai, Generating hard instances of lattice problems. Quad. Mat. 13, 1-32 (2004). Preliminary version in STOC 1996.

[6]

J. Alwen, C. Peikert, Generating shorter bases for hard random lattices, in STACS (2009), pp. 75-86.

[7]

M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval, Key-privacy in public-key encryption, in ASIACRYPT (2001), pp. 566-582.

[8]

D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in EUROCRYPT (2004), pp. 223-238.

[9]

D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in CRYPTO (2004), pp. 443-459.

[10]

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.

Digital Library

[11]

D. Boneh, G.D. Crescenzo, R. Ostrovsky, G. Persiano, Public key encryption with keyword search, in EUROCRYPT (2004), pp. 506-522.

[12]

D. Boneh, R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301-1328 (2007).

Digital Library

[13]

D. Boneh, C. Gentry, M. Hamburg, Space-efficient identity based encryption without pairings, in FOCS (2007), pp. 647-657.

[14]

X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in Public Key Cryptography (2010), pp. 499-517.

[15]

X. Boyen, B. Waters, Anonymous hierarchical identity-based encryption (without random oracles), in CRYPTO (2006), pp. 290-307.

[16]

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.

Digital Library

[17]

D. Cash, D. Hofheinz, E. Kiltz, How to delegate a lattice basis. Cryptology ePrint Archive, Report 2009/351, July 2009. http://eprint.iacr.org/.

[18]

C. Cocks, An identity based encryption scheme based on quadratic residues, in IMA Int. Conf (2001), pp. 360-363.

Digital Library

[19]

G.D. Crescenzo, V. Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in INDOCRYPT (2007), pp. 282-296.

[20]

Y. Dodis, N. Fazio, Public key broadcast encryption for stateless receivers, in ACM Workshop on Digital Rights Management (2002), pp. 61-80.

[21]

C. Gentry, Practical identity-based encryption without random oracles, in EUROCRYPT (2006), pp. 445-464.

Digital Library

[22]

C. Gentry, S. Halevi, Hierarchical identity based encryption with polynomially many levels, in TCC (2009), pp. 437-456.

[23]

C. Gentry, A. Silverberg, Hierarchical ID-based cryptography, in ASIACRYPT (2002), pp. 548-566.

Digital Library

[24]

C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC (2008), pp. 197-206.

Digital Library

[25]

O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, in CRYPTO (1997), pp. 112-131.

[26]

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.

Digital Library

[27]

J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: a ring-based public key cryptosystem, in ANTS (1998), pp. 267-288.

[28]

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.

[29]

S. Hohenberger, B. Waters, Short and stateless signatures from the RSA assumption, in CRYPTO (2009), pp. 654-670.

[30]

J. Horwitz, B. Lynn, Toward hierarchical identity-based encryption, in EUROCRYPT (2002), pp. 466-481.

[31]

H. Krawczyk, T. Rabin, Chameleon signatures, in NDSS (2000).

[32]

G. Leurent, P.Q. Nguyen, How risky is the random-oracle model, in CRYPTO (2009), pp. 445-464.

[33]

V. Lyubashevsky, D. Micciancio, Generalized compact knapsacks are collision resistant, in ICALP (2) (2006), pp. 144-155.

[34]

V. Lyubashevsky, D. Micciancio, Asymptotically efficient lattice-based digital signatures, in TCC (2008), pp. 37-54.

[35]

V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in EUROCRYPT (2010), pp. 1-23.

Digital Library

[36]

D. Micciancio, Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4), 365-411 (2007). Preliminary version in FOCS 2002.

Digital Library

[37]

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).

[38]

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.

Digital Library

[39]

D. Micciancio, B. Warinschi, A linear space algorithm for computing the Hermite normal form, in ISSAC (2001), pp. 231-236.

[40]

M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC (1989), pp. 33-43.

[41]

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in STOC (2009), pp. 333-342.

Digital Library

[42]

C. Peikert, Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive, Report 2009/359, July 2009. http://eprint.iacr.org/.

[43]

C. Peikert, An efficient and parallel Gaussian sampler for lattices, in CRYPTO (2010), pp. 80-97.

Digital Library

[44]

C. Peikert, A. Rosen, Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, in TCC (2006), pp. 145-166.

Digital Library

[45]

C. Peikert, A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in STOC (2007), pp. 478-487.

Digital Library

[46]

C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO (2008), pp. 554-571.

[47]

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).

Digital Library

[48]

O. Regev, On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1-40 (2009). Preliminary version in STOC 2005.

Digital Library

[49]

M. Rückert, Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles, in PQCrypto (2010), pp. 182-200.

Digital Library

[50]

A. Shamir, Identity-based cryptosystems and signature schemes, in CRYPTO (1984), pp. 47-53.

Digital Library

[51]

A. Shamir, Y. Tauman, Improved online/offline signature schemes, in CRYPTO (2001), pp. 355-367.

[52]

D. Stehlé, R. Steinfeld, K. Tanaka, K. Xagawa, Efficient public key encryption based on ideal lattices, in ASIACRYPT (2009), pp. 617-635.

[53]

B. Waters, Efficient identity-based encryption without random oracles, in EUROCRYPT (2005), pp. 114-127.

Digital Library

[54]

B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in CRYPTO (2009), pp. 619-636.

[55]

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.

Cited By

Chen XXu SGao SGuo YYiu SXiao B(2024)FS-LLRS: Lattice-Based Linkable Ring Signature With Forward Security for Cloud-Assisted Electronic Medical RecordsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.345577219(8875-8891)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3455772
Yang MWang HHe D(2024)Puncturable Attribute-Based Encryption From Lattices for Classified Document SharingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337426219(4028-4042)Online publication date: 6-Mar-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3374262
Zhao RMcCarthy SSteinfeld RSakzad AO’Neill M(2024)Quantum-Safe HIBE: Does It Cost a Latte?IEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.334788019(2680-2695)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3347880
Show More Cited By

Bonsai Trees, or How to Delegate a Lattice Basis
1. Security and privacy
2. Theory of computation

Recommendations

Practical Lattice-Based Digital Signature Schemes
Special Issue on Embedded Platforms for Crypto and Regular Papers

Digital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the ...
Bonsai trees, or how to delegate a lattice basis
EUROCRYPT'10: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques

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 ...
Lattice HIBE with Faster Trapdoor Delegation and Applications
Information and Communications Security
Abstract
In this paper, we propose a lattice-based HIBE scheme in the standard model with faster trapdoor delegation. It is proven secure under the Learning With Errors assumption. Inspired by Canetti et al.’s transformation (Eurocrypt’03), an HIBE can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 25, Issue 4

October 2012

223 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 2012 International Association for Cryptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen XXu SGao SGuo YYiu SXiao B(2024)FS-LLRS: Lattice-Based Linkable Ring Signature With Forward Security for Cloud-Assisted Electronic Medical RecordsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.345577219(8875-8891)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3455772
Yang MWang HHe D(2024)Puncturable Attribute-Based Encryption From Lattices for Classified Document SharingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337426219(4028-4042)Online publication date: 6-Mar-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3374262
Zhao RMcCarthy SSteinfeld RSakzad AO’Neill M(2024)Quantum-Safe HIBE: Does It Cost a Latte?IEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.334788019(2680-2695)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3347880
Ma SZhao ZWang NZha C(2024)Lattice-Based CP-ABE for Optimal Broadcast Encryption With Polynomial-Depth CircuitsIET Information Security10.1049/ise2/63335082024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1049/ise2/6333508
Jin RQu LChen RYang ZWang Y(2024)A lattice-based forward secure IBE scheme for Internet of thingsInformation Sciences: an International Journal10.1016/j.ins.2023.120083660:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.ins.2023.120083
Cao CWang FXiao HWang Y(2024)Secure and efficient vehicle data downloading scheme with privacy-preserving in VANETsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110610250:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110610
Soni LChandra HGupta DKeval R(2024)Quantum-resistant public-key encryption and signature schemes with smaller key sizesCluster Computing10.1007/s10586-022-03955-y27:1(285-297)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10586-022-03955-y
Emura K(2024)Generic Construction of Forward Secure Public Key Authenticated Encryption with Keyword SearchApplied Cryptography and Network Security10.1007/978-3-031-54770-6_10(237-256)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_10
Zhang JCui X(2024)LBCSCTransactions on Emerging Telecommunications Technologies10.1002/ett.504035:10Online publication date: 9-Oct-2024
https://dl.acm.org/doi/10.1002/ett.5040
Yang NTian Y(2023)Identity-Based Unidirectional Collusion-Resistant Proxy Re-Encryption from U-LWESecurity and Communication Networks10.1155/2023/37659342023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/3765934
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents