International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Generating Shorter Bases for Hard Random Lattices

Joël Alwen
Chris Peikert
Search ePrint
Search Google
Abstract: We revisit the problem of generating a ``hard'' random lattice together with a basis of relatively short vectors. This problem has gained in importance lately due to new cryptographic schemes that use such a procedure for generating public/secret key pairs. In these applications, a shorter basis directly corresponds to milder underlying complexity assumptions and smaller key sizes. The contributions of this work are twofold. First, using the \emph{Hermite normal form} as an organizing principle, we simplify and generalize an approach due to Ajtai (ICALP 1999). Second, we improve the construction and its analysis in several ways, most notably by tightening the length of the output basis essentially to the optimum value.
  title={Generating Shorter Bases for Hard Random Lattices},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Lattices, average-case hardness, Hermite normal form, cryptography},
  note={STACS 2009 14225 received 12 Dec 2008},
  author={Joël Alwen and Chris Peikert},