DIMACS Theoretical Computer Science Seminar

Title: BCH Codes, Augmented Tensor Products and Hardness of the Shortest Vector Problem in Lattices

Speaker: Subhash Khot, IAS

Date: April 12, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The Shortest Vector Problem in lattices has been studied by mathematicians for two centuries. Given a basis for an n-dimensional lattice, the problem is to find the shortest non-zero vector in the lattice. The approximation version of the problem asks for a non-zero lattice vector that is guaranteed to be within a certain factor of the shortest vector.

There is a rich set of results associated with SVP. For example,

  1. Gauss' algorithm that works for 2-dimensional lattices.
  2. Minkowski's Convex Body Theorem that shows existence of a short lattice vector.
  3. The famous LLL algorithm of Lenstra, Lenstra and Lovasz that achieves 2^n approximation to SVP. It was improved to 2^{o(n)} by Schnorr. This algorithm has numerous applications in mathematics, computer science and cryptography.
  4. Ajtai's reduction from worst-case hardness of approximating SVP to its average case hardness.
  5. Ajtai-Dwork's public-key cryptosystem based on (conjectured) worst case hardness of approximating SVP. Also, a recent alternate construction by Regev.
  6. Results showing that a gap-version of SVP with factor n or \sqrt{n} is "unlikely" to be NP-hard, e.g. Lagarias, Lenstra and Schnorr; Goldreich and Goldwasser; and recently Aharonov and Regev.

However, there has been very little progress in actually proving hardness of approximation results for SVP. Even the NP-hardness of exact version of SVP came only in 1998 (by Ajtai). It was strengthened to a hardness of approximation result with factor \sqrt{2} by Micciancio. This left a huge gap of \sqrt{2} vs 2^{o(n)} between the best hardness result and the best algorithmic result.

In this talk, we greatly improve the hardness factor. We show that assuming NP \not\in BPP, there is no constant factor approximation for SVP (in polytime). Assuming NP \not\in BPTIME(2^{polylog n}}, we show that SVP has no approximation with factor 2^{(\log n)^{1/2-\eps}} where \eps > 0 is an arbitrarily small constant.

We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves *some* constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to an arbitrarily large constant assuming NP \not\in BPP, and to factor 2^{(\log n)^{1/2-\epsilon}} assuming the stronger complexity assumption.

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html