Paper 2010/591

Bonsai Trees, or How to Delegate a Lattice Basis

David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert

Abstract

We introduce a new \emph{lattice-based} cryptographic structure called a \emph{bonsai tree}, and use it to resolve some important open problems in the area. Applications of bonsai trees include: \begin{itemize} \item An efficient, stateless `hash-and-sign' signature scheme in the \emph{standard model} (i.e., no random oracles), and \item The first \emph{hierarchical} identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. \end{itemize} Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.

Note: Updated version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of paper in Eurocrypt 2010.
Keywords
latticestrapdoor functionssignatureshierarchical identity-based encryption
Contact author(s)
cpeikert @ cc gatech edu
History
2011-06-14: last of 2 revisions
2010-11-23: received
See all versions
Short URL
https://ia.cr/2010/591
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/591,
      author = {David Cash and Dennis Hofheinz and Eike Kiltz and Chris Peikert},
      title = {Bonsai Trees, or How to Delegate a Lattice Basis},
      howpublished = {Cryptology ePrint Archive, Paper 2010/591},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/591}},
      url = {https://eprint.iacr.org/2010/591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.