Lattice problem

Summary

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector space (often \mathbb{Q}^n) or free modules (often \mathbb{Z}^n) are generally considered. For all the problems below, assume that we are given (in addition to other more specific inputs) a basis for the vector space V and a no

Official source

https://en.wikipedia.org/wiki/Lattice_problem

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (9)

Related publications

Related people

Related units

Related concepts (6)

Related concepts

Related courses (1)

Related courses

Related lectures (2)

Related lectures

A sieve algorithm based on overlattices

Anja Annemone Becker

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 n in time 2(0.3774n) using memory 2(0.2925n). Moreover, the algorithm is straightforward to parallelize on most computer architectures.

Cambridge Univ Press2014

We give a randomized 2^{n+o(n)}-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic O(4^n)-time and O(2^n)-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2^(n/2) vectors from the discrete Gaussian distribution at any parameter in 2^(n+o(n)) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. We also show that our DGS algorithm implies a 2^(n+o(n))-time algorithm that approximates the Closest Vector Problem to within a factor of 1.97. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate 2^(n/2) discrete Gaussian samples in just 2^(n/2+o(n)) time and space. Among other things, this implies a 2^(n/2+o(n))-time and space algorithm for 1.93-approximate decision SVP.

ACM2015

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique lattices, and a proof that the decision version of uSVP defined by Cai [4] is in co-NP for n(1/4)-unique lattices. (C) 2016 Published by Elsevier B.V.

Elsevier2016