Paper 2008/333

Explicit hard instances of the shortest vector problem

Johannes Buchmann, Richard Lindner, Markus Rückert, and Michael Schneider

Abstract

Building upon a famous result due to Ajtai, we propose a sequence of lattice bases with growing dimension, which can be expected to be hard instances of the shortest vector problem (SVP) and which can therefore be used to benchmark lattice reduction algorithms. The SVP is the basis of security for potentially post-quantum cryptosystems. We use our sequence of lattice bases to create a challenge, which may be helpful in determining appropriate parameters for these schemes.

Note: The revised version describes a modified sequence of lattices of increasing dimension with a better hardness result (theoretically and practically). This modification gives rise to an improved lattice challenge with even harder instances, which will be made available end of 2008. The previous challenge will remain at http://www.latticechallenge.org.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. PQCrypto 2008 -- The Second international Workshop on Post-Quantum Cryptography
Keywords
Lattice reductionlattice-based cryptographychallenge
Contact author(s)
rueckert @ cdc informatik tu-darmstadt de
History
2008-12-01: last of 2 revisions
2008-08-03: received
See all versions
Short URL
https://ia.cr/2008/333
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/333,
      author = {Johannes Buchmann and Richard Lindner and Markus Rückert and Michael Schneider},
      title = {Explicit hard instances of the shortest vector problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/333},
      year = {2008},
      url = {https://eprint.iacr.org/2008/333}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.