Cryptology ePrint Archive: Report 2010/591

Bonsai Trees, or How to Delegate a Lattice Basis

David Cash and Dennis Hofheinz and 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.

Category / Keywords: public-key cryptography / lattices, trapdoor functions, signatures, hierarchical identity-based encryption

Publication Info: Full version of paper in Eurocrypt 2010.

Date: received 21 Nov 2010, last revised 14 Jun 2011

Contact author: cpeikert at cc gatech edu

Available format(s): PDF | BibTeX Citation

Note: Updated version.

Version: 20110614:195353 (All versions of this report)

Short URL: ia.cr/2010/591

Discussion forum: Show discussion | Start new discussion