International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Explicit hard instances of the shortest vector problem

Authors:
Johannes Buchmann
Richard Lindner
Markus Rückert
Michael Schneider
Download:
URL: http://eprint.iacr.org/2008/333
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-18086,
  title={Explicit hard instances of the shortest vector problem},
  booktitle={IACR Eprint archive},
  keywords={foundations /  Lattice reduction, lattice-based cryptography, challenge},
  url={http://eprint.iacr.org/2008/333},
  note={PQCrypto 2008 -- The Second international  Workshop on Post-Quantum Cryptography rueckert@cdc.informatik.tu-darmstadt.de 14214 received 1 Aug 2008, last revised 1 Dec 2008},
  author={Johannes Buchmann and Richard Lindner and Markus Rückert and Michael Schneider},
  year=2008
}