Project: Complexity of lattice problems

Investigator: D. Micciancio

Ph.D. students: V. Lyubashevsky, Yi-Kai Liu, (B. Warinschi)

Other collaborators: V. Guruswami, O. Regev, U. Feige, O. Goldreich, S. Goldwasser, S. Safra, J.-P. Seifert

Funding: Micciancio’s NSF CAREER Award, Sloan Research Fellowship, (Hellman Fellowship)

Summary: The goal of the Complexity of lattice problems project is to identify computational problems on lattices that are computationally intractable, e.g., NP-hard. Identifying and studying computationally hard problems is important for two different reasons:

1. Getting a better understanding of the hard instances is useful to direct algorithmic efforts in the search of good solutions to problem instances of practical interest
2. Intractable problems can be used as a source of computational hardness to be used in cryptographic applications, i.e., in the construction of cryptographic functions that are hard to break. (See also the Lattice based cryptography project.)

As part of this project we are investigating the most important computational problems on lattices, and proved that many of them are NP-hard to solve even in an approximate sense. Compuational problems considered so far include:

• The Shortest Vector Problem (SVP)
• The Closest Vector Problems with Preprocessing (CVPP)
• The Covering Radius Problem (CRP)

For an introduction to the computational complexity of lattice problems, we refer the reader to the book Complexity of Lattice Problems: A Cryptographic Perspective (Kluwer, 2002) by D. Micciancio and S. Goldwasser.

The Shortest Vector Problem (SVP)

The shortest vector problem is the most famous computational problem on lattices, and it has been studied by mathematicians for centuries since the time of Gauss (in the equivalent formulation of minimization of a quadratic form). The NP-hardness of SVP was conjectured by van Emde Boas in 1981, and remained one of the most important open problems in the area for almost two decades.

• In The shortest vector problem is NP-hard to approximate to within some constant (SIAM Journal on Computing, 2001) D. Micciancio proved that SVP is NP-hard to solve even approximately, for any approximation factor up to sqare root of 2.

Another long standing open problem in the area was the relation between SVP and it inhomogeneous counterpart, the Closest Vector Problem (CVP). Although it was commonly believed that CVP is a harder problem than SVP, no theoretical evidence supporting such a claim was known till recently. In fact, in 1986 Babai had posed the problem of reducing SVP to CVP even in a very weak sense: show that if CVP can be solved almost exactly in polynomial time, then SVP can be solved in polynomial time within factors subexponential in the dimension. We positively resolved this conjecture in a very strong sense by giving a dimension preserving and approximation preserving polynomial time reduction from SVP to CVP:

• In Approximating shortest lattice vectors is not harder than approximating closest lattice vectors (Information Processing Letters, 1999) D. Micciancio with collaborators O.Goldreich, S. Safra and J.-P. Seifert, proved that SVP is not harder than CVP in a very strong sense: any algorithm to solve CVP (even approximately within a factor g) can be efficiently converted into an algorithm to solve SVP within the same approximation factor g.

The Closest Vector Problem with Preprocessing (CVPP)

The Closest Vector Problem (CVP) is the inhomogeneous counterpart of SVP: given a lattice L and a target point in space y, find the lattice point in L closest to y. This is a classic NP-hard combinatorial optimization problem: it was proved NP-hard to solve exactly by van Emde Boas in 1981, and the best currently known inapproximability result (by Dinur, Kindler, Raz, Safra, 2003) shows the NP-harness of the problem within any subpolynomial factor of the form n^O(1/log\ log\ n)^.

The Closest Vector Problem with Preprocessing (CVPP) poses the question whether the hardness of CVP comes from the fact that the lattice L is not known in advance, or CVP can be hard to solve even for a fixed family of lattices. Namely, given a sequence of lattices L₁,…,L_n, … in increasing dimension n, CVPP asks if there is a polynomial time algorithm that on input an n-dimensional vector y finds the lattice point in L_n closest to y. For certain families of lattices, CVPP can be efficiently solved: for example, if L_n=Zⁿ is the lattice of all integer vectors, then the closest lattice point to y can be easily found by rounding each coordinate of y to the closest integer.

• In The hardness of the closest vector problem with preprocessing (IEEE Transactions on Information Theory, 2001), D. Micciancio initiated the study of CVPP and proved that CVPP is NP-hard to solve exactly, i.e., there is a specific sequence of lattices {L_n} such that finding lattice points closest to a given target y is NP-hard.

A natural question is whether CVPP is not only NP-hard to solve exactly, but also NP-hard to solve in an approximate sense.

• In The inapproximability of lattice and coding problems with preprocessing (J. of Computer and System Sciences, JCSS 2004) D. Micciancio and collaborator U. Feige, proved the first inapproximability result for CVPP, showing that approximating CVPP is NP-hard for any approximation factor up to square root of 5/3.

The best currently known inapproximability result for CVPP is by O. Regev, for factors up to square root of 3. Proving the NP-hardness of CVPP for any constant approximation factor is an important open problem in the area. On the positive side, it is interesting to construct interesting family of lattices that are easily decodable, i.e., such that CVPP can be solved efficiently.

• In Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor (SIAM J. on Computing, SICOMP 2004) D. Micciancio introduced (motivated by cryptographic applications) the special class of “almost perfect lattices”, and asks for the efficient construction of easily decodable almost perfect lattices. Informally, a lattice is almost perfect if the covering radius is not much bigger than the packing radius. The integer lattice Zⁿ is easily decodable, but the ratio between the covering and packing radius is rather large (sqrt(n)). In this same paper, Micciancio gives the first construction of easily decodable lattices with ratio between the covering and packing radius asymptotically smaller than sqrt(n).

The ratio betwteen the covering and packing radius of the lattices defined in (Micciancio, SICOMP 2004) is sqrt(n log log n / log n). It is an interesting open problem (both for cryptographic and coding theory applications) to find better constructions achieving smaller (possibly constant) ratios between the two radii.

The Covering Radius Problem (CRP)

The covering radius is the smallest radius such that spheres centered at all lattice points cover the entire space. The covering radius of lattices has been extensively studied by mathematicians, but it has received so far little attention from a computational point of view. Recently, (Micciancio, SICOMP 2004) has brought attention to this prioblem because of potential cryptographic applications. The problem is especially interesting because the covering radius of a lattice is not even known to be efficiently computable in non-deterministic polynomial time (NP), so the exact version of the problem appears to be extremely hard.

• In The complexity of the covering radius problem (Computational Complexity, 2005) D. Micciancio with collaborators V. Guruswami and O. Regev, started the systematic study of the computational complexity of approximating the covering radius of point lattices and proved many results for various values of the approximation factor. These results include:

  1. A probabilistic exponential time algorithm for any constant factor g > 1
  2. An interactive (AM) proof system for constant factor g = 2 to show that the covering radius is small
  3. An interactive (coAM) proof systen for factors g = O(sqrt(n / log n)) to show that the covering radius is large
  4. Non-interactive (NP and coNP) proof systems for factors g = O(sqrt(n))
  5. A random polynomial time algorithm for factors g = exp(O(n log log n / log n))

  
  

Proving the NP-hardness of the covering radius problem for lattices (even in its exact version) is currently an open problem. The analogous problems for linear codes is known to be NP-hard for any constant approximation factor, and Pi2-hard for some constant approximation factor. (See Complexity of Coding Problems project page.)