Hardness of approximating the shortest vector problem in lattices

ABSTRACT

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓp norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2^{poly(log n)}), we show that there is no polynomial-time algorithm with approximation ratio 2^{(log n)1/2−ε} where n is the dimension of the lattice and ε > 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 2^{(log n)1/2-ε}.

REFERENCES

• 1: Dorit Aharonov , Oded Regev, Lattice Problems in NP " coNP, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.362-371, October 17-19, 2004 [doi>10.1109/FOCS.2004.35]
• 2: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 3: 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]
• 4: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 5: 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]
• 6: Alon, N., Spencer, J., and Erdos, P. 1991. The Probabilistic Method. Wiley-Interscience Series.
• 7: 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]
• 8: Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 625--635.
• 9: Jin-Yi Cai, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Discrete Applied Mathematics, v.126 n.1, p.9-31, March 2003 [doi>10.1016/S0166-218X(02)00216-0]
• 10: Jin-yi Cai , Ajay P. Nerurkar, An Improved Worst-Case to Average-Case Connection for Lattice Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.468, October 19-22, 1997
• 11: 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]
• 12: 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]
• 13: I. Dinur , G. Kindler , S. Safra, Approximating-CVP to within Almost-Polynomial Factors is NP-Hard, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.99, November 08-11, 1998
• 14: Ilya Dumer , Daniele Micciancio , Madhu Sudan, Hardness of Approximating the Minimum Distance of a Linear Code, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.475, October 17-18, 1999
• 15: Gauss, C. 1801. Disquisitiones arithmetica (Leipzig, 1801: art. 171). Yale Univ. Press. (English translation by A. A. Clarke, 1966.)
• 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: O. Goldreich , D. Micciancio , S. Safra , J. -P. Seifert, Approximating shortest lattice vectors is not harder than approximating closet lattice vectors, Information Processing Letters, v.71 n.2, p.55-61, July 30, 1999 [doi>10.1016/S0020-0190(99)00083-6]
• 18: Hastad, J. 1988. Dual vectors and lower bounds for the nearest lattice point problem. Combinatorica 8, 75--81.
• 19: Ravi Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.193-206, December 1983 [doi>10.1145/800061.808749]
• 20: 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]
• 21: Subhash Khot, Hardness of Approximating the Shortest Vector Problem in High Lp Norms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.290, October 11-14, 2003
• 22: Kumar, R., and Sivakumar, D. 2001. Complexity of SVP---A reader's digest. Complexity Theory Column, L. Hemaspaandra, Ed. SIGACT News 32, 3.
• 23: Lagarias, J., Lenstra, H., and Schnorr, C. 1990. Korkine--Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10, 333--348.
• 24: J. C. Lagarias , A. M. Odlyzko, Solving low-density subset sum problems, Journal of the ACM (JACM), v.32 n.1, p.229-246, Jan. 1985 [doi>10.1145/2455.2461]
• 25: Landau, S., and Miller, G. 1985. Solvability of radicals is in polynomial time. J. Comput. Syst. Sci. 30, 2, 179--208.
• 26: Lenstra, A., Lenstra, H., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 513--534.
• 27: Lenstra, H. 1981. Integer programming with a fixed number of variables. Tech. Report 81-03. Univ. of Amsterdam, Amsterdam, The Netherland.
• 28: 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]
• 29: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 30: Minkowski, H. 1910. Geometrie der zahlen. Tuebner.
• 31: Oded Regev, New lattice based cryptographic constructions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780603]
• 32: 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]
• 33: van Emde Boas, P. 1981. Another NP-complete problem and the complexity of computing short vectors in a lattice. Tech. Report 81-04. Mathematische Instiut, Univ. of Amsterdam, Amsterdam, The Netherland.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, cryptography, hardness of approximation, lattices, shortest vector problem