Cryptology ePrint Archive: Report 2008/333

Explicit hard instances of the shortest vector problem

Johannes Buchmann and Richard Lindner and Markus Rückert

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.

Category / Keywords: foundations / Lattice reduction, lattice-based cryptography, challenge

Publication Info: PQCrypto 2008 -- The Second international Workshop on Post-Quantum Cryptography

Date: received 1 Aug 2008, last revised 6 Aug 2008

Contact author: rueckert at cdc informatik tu-darmstadt de

Available formats: PDF | BibTeX Citation

Note: Added a note from Damien Stehlé regarding performance issues with fpLLL.

Version: 20080806:114909 (All versions of this report)

Discussion forum: Show discussion | Start new discussion