Lattices that admit logarithmic worst-case to average-case connection factors

ABSTRACT

We exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n-dimensional lattices in the worst case, for γ(n) = O(√log n). The previously best known factor for any non-trivial class of lattices was γ(n) = Õ(n).

Our results apply to families of lattices having special algebraic structure. Specifically, we consider lattices that correspond to ideals in the ring of integers of an algebraic number field. The worst-case problem we rely on is to find approximate shortest vectors in these lattices, under an appropriate form of preprocessing of the number field.

For the connection factors γ(n) we achieve, the corresponding decision problems on ideal lattices are not known to be NP-hard; in fact, they are in P. However, the search approximation problems still appear to be very hard. Indeed, ideal lattices are well-studied objects in computational number theory, and the best known algorithms for them seem to perform no better than the best known algorithms for general lattices.

To obtain the best possible connection factor, we instantiate our constructions with infinite families of number fields having constant root discriminant. Such families are known to exist and are computable, though no efficient construction is yet known. Our work motivates the search for such constructions. Even constructions of number fields having root discriminant up to O(n^2/3-ε) would yield connection factors better than Õ(n).

As an additional contribution, we give reductions between various worst-case problems on ideal lattices, showing for example that the shortest vector problem is no harder than the closest vector problem. These results are analogous to previously-known reductions for general lattices.

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: 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: Adi Akavia , Oded Goldreich , Shafi Goldwasser , Dana Moshkovitz, On basing one-way functions on NP-hardness, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132614]
• 7: S. Alaca and K.S. Williams. Introductory Algebraic Number Theory. Cambridge University Press, November 2003.
• 8: W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625--635, 1993.
• 9: W. Banaszczyk. Inequalites for convex bodies and polar reciprocal lattices in Rⁿ. Discrete & Computational Geometry, 13:217--231, 1995.
• 10: E. Bayer-Fluckiger. Personal communication.
• 11: E. Bayer-Fluckiger. A Panorama of Number Theory Or The View from Baker's Garden, chapter 11, pages 168--184. Cambridge University Press, September 2002.
• 12: J. Bruck and M. Naor. The hardness of decoding linear codes with preprocessing. IEEE Transactions on Information Theory, 36(2):381--385, 1990.
• 13: 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]
• 14: 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
• 15: 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]
• 16: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 17: Henri Cohen , Francisco Diaz y Diaz , Michel Olivier, A Table of Totally Complex Number Fields of Small Discriminants, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.381-391, June 21-25, 1998
• 18: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 19: 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]
• 20: 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]
• 21: O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. Electronic Colloquium on Computational Complexity (ECCC), 3(42), 1996.
• 22: 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]
• 23: V. Guruswami. Constructions of codes from number fields. IEEE Transactions on Information Theory, 49(3):594--603, 2003.
• 24: D. Gutfreund and A. Ta-Shma. New connections between derandomization, worst-case complexity and average-case complexity. Technical Report TR06-108, Electronic Colloquium on Computational Complexity, 2006.
• 25: J.H.W. Lenstra. Algorithms in algebraic number theory. Bulletin of the American Mathematical Society, 26(2):211--244, April 1992.
• 26: Sean Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060660]
• 27: Ishay Haviv , Oded Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250859]
• 28: 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]
• 29: A.K. Lenstra, H.W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515--534, December 1982.
• 30: H.W. Lenstra. Codes from algebraic number fields. In M. Hazewinkel, J.K. Lenstra, and L.G. L.T. Meertens, editors, Mathematics and computer science II, Fundamental contributions in the Netherlands since 1945, CWI Monograph 4, pages 95--104. Elsevier, North-Holland, Amsterdam, 1986.
• 31: V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 144--155. Springer, 2006. Full version in ECCC Report TR05-142.
• 32: 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]
• 33: D. Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Transactions on Information Theory, 47(3):1212--1215, 2001.
• 34: Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.356-365, November 16-19, 2002
• 35: Daniele Micciancio, Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor, SIAM Journal on Computing, v.34 n.1, p.118-169, 2005 [doi>10.1137/S0097539703433511]
• 36: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.372-381, October 17-19, 2004 [doi>10.1109/FOCS.2004.72]
• 37: J. Milnor and D. Husemoller. Symmetric Bilinear Forms. Springer, 1973.
• 38: R.A. Mollin. Algebraic Number Theory. CRC Press, 1999.
• 39: Chris Peikert, Limits on the Hardness of Lattice Problems in \ell _p Norms, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.333-346, June 13-March 16, 2007 [doi>10.1109/CCC.2007.12]
• 40: C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, volume 3876 of Lecture Notes in Computer Science, pages 145--166. Springer, 2006. Full version in ECCC TR05-158.
• 41: 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]
• 42: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 43: 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]
• 44: P. Roquette. On class field towers, chapter IX, pages 231--249. Academic Press, 1967.
• 45: 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]
• 46: D. Simon. Personal communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory

Keywords:
algebraic number theory, lattices, worst-case to average-case reductions