Lattice problems and norm embeddings

ABSTRACT

We present reductions from lattice problems in the l₂ norm to the corresponding problems in other norms such as l₁, l_∞ (and in fact in any other l_p norm where 1 ≤ p ≤ ∞). We consider lattice problems such as the Shortest Vector Problem, Shortest Independent Vector Problem, Closest Vector Problem and the Closest Vector Problem with Preprocessing. Most reductions are simple and follow from known constructions of embeddings of normed spaces.Among other things, our reductions imply that the Shortest Vector Problem in the l₁ norm and the Closest Vector Problem with Preprocessing in the l_∞ norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2-ε, while no hardness result was known for the latter problem.

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: 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: M. Ajtai. Worst-case complexity, average-case complexity and lattice problems. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), pages 421--428, 1998.
• 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: M. Alekhnovich, S. Khot, G. Kindler, and N. K. Vishnoi. Hardness of approximating the closest vector problem with pre-processing. submitted, 2005.
• 7: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 8: 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]
• 9: K. Ball. An elementary introduction to modern convex geometry. In Flavors of geometry, volume 31 of Math. Sci. Res. Inst. Publ., pages 1--58. Cambridge Univ. Press, Cambridge, 1997.
• 10: Bonnie Berger, The Fourth Moment Method, SIAM Journal on Computing, v.26 n.4, p.1188-1207, Aug. 1997 [doi>10.1137/S0097539792240005]
• 11: Johannes Blömer , Jean-Pierre Seifert, On the complexity of computing short linearly independent vectors and short bases in a lattice, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.711-720, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301441]
• 12: 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]
• 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: A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123--160. Jerusalem Academic Press, Jerusalem, 1961.
• 16: Uriel Feige , Daniele Micciancio, The inapproximability of lattice and coding problems with preprocessing, Journal of Computer and System Sciences, v.69 n.1, p.45-67, August 2004 [doi>10.1016/j.jcss.2004.01.002]
• 17: T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53--94, 1977.
• 18: 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]
• 19: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 20: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 21: Piotr Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: W. B. Johnson and G. Schechtman. Finite dimensional subspaces of Lp. In Handbook of the geometry of Banach spaces, Vol. I, pages 837--870. North-Holland, Amsterdam, 2001.
• 23: 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]
• 24: 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
• 25: Subhash Khot, Hardness of Approximating the Shortest Vector Problem in Lattices, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.126-135, October 17-19, 2004 [doi>10.1109/FOCS.2004.31]
• 26: 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]
• 27: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515--534, 1982.
• 28: H. W. Lenstra, Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538--548, 1983.
• 29: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 30: D. Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Trans. Inform. Theory, 47(3):1212--1215, 2001.
• 31: 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]
• 32: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 33: O. Regev. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Transactions on Information Theory, 50(9):2031--2037, 2004. Preliminary version in CCC'03.
• 34: Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
• 35: W. Rudin. Trigonometric series with gaps. Indiana Univ. Math. J., 9:203--227, 1960.
• 36: 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]
• 37: 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:
embedding, hardness of approximation, lattices, norms