Tensor-based hardness of the shortest vector problem to within almost polynomial factors

ABSTRACT

We show that unless NP ⊆ RTIME (2^{poly(log n)}), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe l_p norm (1 ≤q p<∞) to within a factor of 2^{(log n)1-ε}. This improves the previous best factor of 2^(logn)1/2-ε under the same complexity assumption due to Khot. Under the stronger assumption NP ࣰ RSUBEXP, we obtain a hardness factor of n^{c/log log n} for some c > 0.

Our proof starts with Khot's SVP instances from that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product oflattices. The main novel part is in the analysis, where we show that Khot's lattices behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.

REFERENCES

• 1: Dorit Aharonov , Oded Regev, Lattice problems in NP ∩ coNP, Journal of the ACM (JACM), v.52 n.5, p.749-765, September 2005 [doi>10.1145/1089023.1089025]
• 2: Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.10-19, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276705]
• 3: M. Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1--32. Dept. Math., Seconda Univ. Napoli, Caserta, 2004.
• 4: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 5: N. Alon and J.H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000.
• 6: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 7: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 8: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 9: R. Bhatia. Matrix Analysis. Springer, 1997.
• 10: Jin-Yi Cai , Ajay Nerurkar, Approximating the SVP to within a factor (1+1/dimE) is NP-Hard under randomized reductions, Journal of Computer and System Sciences, v.59 n.2, p.221-239, Oct. 1999 [doi>10.1006/jcss.1999.1649]
• 11: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 12: E. de Shalit and O. Parzanchevski. On tensor products of semistable lattices. Preprint, 2006.
• 13: I. Dinur. Approximating SVP_∞ to within almost-polynomial factors is NP-hard. Theoretical Computer Science, 285(1):55--71, 2002.
• 14: I. Dinur , G. Kindler , R. Raz , S. Safra, Approximating CVP to Within Almost-Polynomial Factors is NP-Hard, Combinatorica, v.23 n.2, p.205-243, April 2003 [doi>10.1007/s00493-003-0019-y]
• 15: I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory, 49(1):22--37, 2003.
• 16: Oded Goldreich , Shafi Goldwasser, On the limits of nonapproximability of lattice problems, Journal of Computer and System Sciences, v.60 n.3, p.540-563, June 2000 [doi>10.1006/jcss.1999.1686]
• 17: Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
• 18: Subhash Khot, Hardness of approximating the shortest vector problem in lattices, Journal of the ACM (JACM), v.52 n.5, p.789-808, September 2005 [doi>10.1145/1089023.1089027]
• 19: A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515--534, 1982.
• 20: Daniele Micciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant, SIAM Journal on Computing, v.30 n.6, p.2008-2035, 2001 [doi>10.1137/S0097539700373039]
• 21: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 22: J. Milnor and D. Husemoller. Symmetric bilinear forms. Springer-Verlag, Berlin, 1973.
• 23: H. Minkowski. Geometrie der Zahlen. I@. B. G. Teubner, Leipzig, 1896.
• 24: Oded Regev , Ricky Rosen, Lattice problems and norm embeddings, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132581]
• 25: C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8]
• 26: P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math Inst., University Of Amsterdam, Amsterdam, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
hardness of approximation, lattices, tensor product