Paper 2009/351

How to Delegate a Lattice Basis

David Cash, Dennis Hofheinz, and Eike Kiltz


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.

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

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Lattice-Based CryptographyIdentity-Based Cryptography
Contact author(s)
cdc @ gatech edu
2009-07-24: revised
2009-07-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Cash and Dennis Hofheinz and Eike Kiltz},
      title = {How to Delegate a Lattice Basis},
      howpublished = {Cryptology ePrint Archive, Paper 2009/351},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.