We give a @math -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on @math -dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic @math -time and @math -space algorithm of Micciancio and Voulgaris. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [ADRS15] to solve the problem of discrete Gaussian sampling over lattice shifts, @math , with very low parameters. While the actual algorithm is a natural generalization of [ADRS15], the analysis uses substantial new ideas. This yields a @math -time algorithm for approximate CVP for any approximation factor @math . Second, we show that the approximate closest vectors to a target vector @math can be grouped into "lower-dimensional clusters," and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that "behaves well with these clusters." Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.
The paper presents an algorithm for solving Integer Programming problems whose running time depends on the number n of variables as nOn. This is done by reducing an n variable problem to 2n5i 2 problems in n-i variables for some i greater than zero chosen by the algorithm. The factor of On5 2 “per variable” improves the best previously known factor which is exponential in n. Minkowski's Convex Body theorem and other results from Geometry of Numbers play a crucial role in the algorithm. Several related algorithms for lattice problems are presented. The complexity of these problems with respect to polynomial-time reducibilities is studied. Letλi(L), λi(L*) denote the successive minima of a latticeL and its reciprocal latticeL*, and let [b1,..., b n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that Open image in new window and Open image in new window , where Open image in new window andγj denotes Hermite's constant. As a consequence the inequalities Open image in new window are obtained forn≥7. Given a basisB of a latticeL in ℝ m of rankn andx∃ℝ m , we define polynomial time computable quantitiesλ(B) andΜ(x,B) that are lower bounds for λ1(L) andΜ(x,L), whereΜ(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL*, then λ1(L)≤γ n * λ(B) and Open image in new window . Enumeration algorithms are the best currently known methods to solve lattice problems, both in theory (within the class of polynomial space algorithms), and in practice (where they are routinely used to evaluate the concrete security of lattice cryptography). However, there is an uncomfortable gap between our theoretical understanding and practical performance of lattice point enumeration algorithms. The algorithms typically used in practice have worst-case asymptotic running time 2O(n2), but perform extremely well in practice, at least for all values of the lattice dimension for which experimentation is feasible. At the same time, theoretical algorithms (Kannan, Mathematics of Operation Research 12(3):415-440, 1987) are asymptotically superior (achieving 2O(n log n) running time), but they are never used in practice because they incur a substantial overhead that makes them uncompetitive for all reasonable values of the lattice dimension n. This gap is especially troublesome when algorithms are run in practice to evaluate the concrete security of a cryptosystem, and then experimental results are extrapolated to much larger dimension where solving lattice problems is computationally infeasible. We introduce a new class of (polynomial space) lattice enumeration algorithms that simultaneously achieve asymptotic efficiency (meeting the theoretical nO(n) = 2O(n log n) time bound) and practicality, matching or surpassing the performance of practical algorithms already in moderately low dimension. Key technical contributions that allow us to achieve this result are a new analysis technique that allows us to greatly reduce the number of recursive calls performed during preprocessing (from super exponential in n to single exponential, or even polynomial in n), a new enumeration technique that can be directly applied to projected lattice (basis) vectors, without the need to remove linear dependencies, and a modified block basis reduction method with fast (logarithmic) convergence properties. The last technique is used to obtain a new SVP enumeration procedure with O(nn 2e) running time, matching (even in the constant in the exponent) the optimal worst-case analysis (Hanrot and Stehle, CRYPTO 2007) of Kannan's theoretical algorithm, but with far superior performance in practice. We complement our theoretical analysis with a preliminary set of experiments that not only support our practicality claims, but also allow to estimate the crossover point between different versions of enumeration algorithms, as well as asymptotically faster (but not quite practical) algorithms running in single exponential 2O(n) time and space. Abstract Up to now, the problem of constructing Minkowski reduced lattice bases has been solved only for the two- and three-dimensional case. This paper presents an algorithm to solve the problem for arbitrary dimension. For fixed dimension, the runtime is polynomial. The algorithm hinges on the previous reduction algorithms of Lenstra, Lenstra and Lovasz (1982) and Kannan (1983). Moreover, we shall improve Kannan's algorithm to construct Hermite reduced lattice bases. The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of com- puting a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complex- ity estimates have not been improved since over twenty years. Kannan's algorithm for solving the shortest vector problem (SVP) is in particu- lar crucial in Schnorr's celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryp- tion schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan's algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards pro- viding meaningful key-sizes. In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence no longer to work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case. This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension @math in time @math using memory @math . Moreover, the algorithm is straightforward to parallelize on most computer architectures.