Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Lattices, average-case hardness, Hermite normal form, cryptography

Publication Info: STACS 2009, Theory of Computing Systems 2010

Date: received 12 Dec 2008, last revised 25 Jun 2010

Contact author: cpeikert at alum mit edu

Available formats: PDF | BibTeX Citation

Version: 20100625:174328 (All versions of this report)

Discussion forum: Show discussion | Start new discussion