How to Delegate a Lattice Basis

David Cash; Dennis Hofheinz; Eike Kiltz

Paper 2009/351

How to Delegate a Lattice Basis

David Cash, 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.

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

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Lattice-Based Cryptography Identity-Based Cryptography
Contact author(s): cdc @ gatech edu
History: 2009-07-24: revised; 2009-07-21: received; See all versions
Short URL: https://ia.cr/2009/351
License: CC BY

BibTeX

@misc{cryptoeprint:2009/351,
      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},
      url = {https://eprint.iacr.org/2009/351}
}