Paper 2008/521

Generating Shorter Bases for Hard Random Lattices

Joel Alwen and Chris Peikert

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 to generate public/secret key pairs. In these applications, a shorter basis corresponds to milder underlying complexity assumptions and smaller key sizes. The contributions of this work are twofold. First, we simplify and modularize an approach originally due to Ajtai (ICALP 1999). Second, we improve the construction and its analysis in several ways, most notably by making the output basis asymptotically as short as possible.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. STACS 2009, Theory of Computing Systems 2010
Keywords
Latticesaverage-case hardnessHermite normal formcryptography
Contact author(s)
cpeikert @ alum mit edu
History
2010-06-25: last of 2 revisions
2008-12-16: received
See all versions
Short URL
https://ia.cr/2008/521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/521,
      author = {Joel Alwen and Chris Peikert},
      title = {Generating Shorter Bases for Hard Random Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2008/521},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/521}},
      url = {https://eprint.iacr.org/2008/521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.