License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1832
URN: urn:nbn:de:0030-drops-18327
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1832/
Go to the corresponding LIPIcs Volume Portal

Alwen, Joel ; Peikert, Chris

Generating Shorter Bases for Hard Random Lattices

pdf-format:
09001.AlwenJoel.1832.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{alwen_et_al:LIPIcs:2009:1832,
  author =	{Joel Alwen and Chris Peikert},
  title =	{{Generating Shorter Bases for Hard Random Lattices}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{75--86},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1832},
  URN =		{urn:nbn:de:0030-drops-18327},
  doi =		{10.4230/LIPIcs.STACS.2009.1832},
  annote =	{Keywords: Lattices, Random, Short basis, Average-case hardness, Hermite normal form, Cryptography}
}

Keywords: Lattices, Random, Short basis, Average-case hardness, Hermite normal form, Cryptography
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI