Cryptology ePrint Archive: Report 2009/351

How to Delegate a Lattice Basis

David Cash and Dennis Hofheinz and Eike Kiltz

Abstract: We present a technique, which we call basis delegation, that allows one to use a short basis of a given lattice to derive a new short basis of a related lattice in a secure way. And since short bases for lattices essentially function like cryptographic trapdoors, basis delegation turns out to be a very powerful primitive. As the main application of our technique, we show how to construct hierarchical identity-based encryption (HIBE) that is secure, without random oracles, under the assumption that certain standard lattice problems are hard in the worst case. This construction and its variants constitute the first HIBE schemes from lattices, as well as the first lattice-based constructions of stateless signatures and identity-based encryption without random oracles.

Category / Keywords: public-key cryptography / Lattice-Based Cryptography, Identity-Based Cryptography

Date: received 19 Jul 2009, last revised 24 Jul 2009

Contact author: cdc at gatech edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: [24-07-2009: Bugfix: Lemma 2.1 was cited wrongly]

Version: 20090724:140452 (All versions of this report)

Discussion forum: Show discussion | Start new discussion