Project : cascade
Section: New Results
Foundations
Participants : Nicolas Gama, Phong Nguyen.
Finding Short Lattice Vectors Within Mordell's Inequality, STOC '08
The shortest vector problem (SVP) in a lattice is a famous NP-hard problem of interest to both public-key cryptography and public-key cryptanalysis. Despite its importance, extremely few algorithms are known. This article presents the best polynomial-time algorithm known for approximating SVP. The algorithm, called slide reduction, has a natural interpretation: it can be viewed as an algorithmic version of a mathematical inequality proved by Mordell back in 1944.
The first polynomial-time algorithm for approximating SVP is the celebrated LLL algorithm, published by Lenstra, Lenstra and Lovász in 1982, and referenced by thousands of articles since: the historical applications of LLL were integer programming in fixed dimension, factoring polynomial with rational coefficients, and Diophantine approximation. The LLL algorithm is arguably best described as an algorithmic version of a mathematical inequality discovered by Hermite in 1850, which proved the existence of a constant related to lattice packings, now known as Hermite's constant. The principles and the worst-case output quality of the LLL algorithm are tightly related to Hermite's inequality.
In 1944, Mordell found a simple generalization of Hermite's inequality, which gave rise to better upper bounds on Hermite's constant. This article presents the first true algorithmic analogue of Mordell's inequality: the algorithm is to Mordell's inequality what LLL is to Hermite's inequality. As such, the new algorithm can be viewed as the “right” blockwise generalization of the LLL algorithm. Furthermore, it is simpler than previous blockwise generalizations of LLL, and a tight worst-case analysis is known.
Predicting Lattice Reduction, EUROCRYPT '08
Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.
Sieve Algorithms for the Shortest Vector Problem are Practical, Journal of Mathematical Cryptology 2008
We assess the practicality of the best (theoretical) algorithm
known for exact SVP in low dimension:
the sieve algorithm proposed by Ajtai, Kumar and Sivakumar (AKS)
in 2001. AKS is a randomized algorithm of time and space complexity
2O(n), which is theoretically much lower than the super-exponential
complexity of all alternative SVP algorithms.
Surprisingly, no implementation and no practical analysis of AKS has
ever been reported.
It was in fact widely believed that AKS was impractica.
In this paper, we show that AKS can actually be made practical:
we present a heuristic variant of AKS whose running time is
(4/3 + 
)n polynomial-time operations,
and whose space requirement is (4/3 + )n/2 polynomially
many bits.
Our implementation can experimentally find shortest lattice vectors
up to dimension 50, but is slower than classical alternative SVP
algorithms in these dimensions
