Finding short lattice vectors within mordell's inequality

ABSTRACT

The celebrated Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL) can naturally be viewed as an algorithmic version of Hermite's inequality on Hermite's constant. We present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of Mordell's inequality on Hermite's constant. This achieves a better and more natural approximation factor for the shortest vector problem than Schnorr's algorithm and its transference variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation factor is essentially tight in the worst case.

REFERENCES

• 1: Miklos Ajtai, The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780602]
• 2: 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]
• 3: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 4: H. Cohn and N. Elkies. New upper bounds on sphere packings. I. Ann. of Math. (2), 157(2):689--714, 2003.
• 5: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 6: N. Gama, N. Howgrave-Graham, H. Koy, and P. Q. Nguyen. Rankin's constant and blockwise lattice reduction. In Proceedings of CRYPTO '06, volume 4117 of LNCS, Springer, pages 112--130, 2006.
• 7: N. Gama, N. Howgrave-Graham, and P. Q. Nguyen. Symplectic Lattice Reduction and NTRU. In Proceedings of EUROCRYPT '06, volume 4004 of LNCS, Springer, pages 233--253, 2006.
• 8: N. Gama and P. Q. Nguyen. Predicting Lattice Reduction. In Proceedings of EUROCRYPT '08, LNCS, Springer Verlag, pages 31 -- 51, 2008.
• 9: M. Grötschel, L. Lovasz, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics: Study and Research Texts. Springer-Verlag, Berlin, 1988.
• 10: M. Gruber and C. G. Lekkerkerker. Geometry of Numbers. North-Holland, 1987.
• 11: G. Hanrot and D. Stehle. Worst-case Hermite-Korkine-Zolotarev reduced lattice bases. CoRR, abs/0801.3331, 2008.
• 12: C. Hermite. Extraits de lettres de M. Hermite a M. Jacobi sur differents objets de la theorie des nombres, deuxieme lettre. J. Reine Angew. Math., 40:279--290, 1850. Also available in the first volume of Hermite's complete works, published by Gauthier-Villars.
• 13: 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]
• 14: S. Khot. Inapproximability results for computational problems on lattices. 2007. To appear in NgVa07.
• 15: A. Korkine and G. Zolotareff. Sur les formes quadratiques. Math. Ann., 6:336--389, 1873.
• 16: J. L. Lagrange. Recherches d'arithmetique. Nouveaux Memoires de l'Academie de Berlin, 1773.
• 17: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz. Factoring polynomials with rational coefficients. Mathematische Ann., 261:513--534, 1982.
• 18: L. Lovasz. An Algorithmic Theory of Numbers, Graphs and Convexity, volume 50. SIAM Publications, 1986.
• 19: CBMS-NSF Regional Conference Series in Applied Mathematics.
• 20: J. Martinet. Perfect lattices in Euclidean spaces, volume 327 of Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}. Springer-Verlag, Berlin, 2003.
• 21: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 22: J. Milnor and D. Husemoller. Symmetric bilinear forms. Math. Z, 1973.
• 23: L. J. Mordell. Observation on the minimum of a positive quadratic form in eight variables. J. London Math. Soc., 19:3--6, 1944.
• 24: Phong Q. Nguyen , Jacques Stern, The Two Faces of Lattices in Cryptology, Revised Papers from the International Conference on Cryptography and Lattices, p.146-180, March 29-30, 2001
• 25: P. Q. Nguyen and B. Vallee, editors. LLL+25. Information Security and Cryptography. Springer, 2008. To appear.
• 26: P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. J. of Mathematical Cryptology, 2008. To appear.
• 27: O. Regev. On the complexity of lattice problems with polynomial approximation factors. 2007. To appear in NgVa07.
• 28: 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]
• 29: C. P. Schnorr , M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Mathematical Programming: Series A and B, v.66 n.2, p.181-199, Sept. 7, 1994 [doi>10.1007/BF01581144]
• 30: Gilles Villard, Parallel lattice basis reduction, Papers from the international symposium on Symbolic and algebraic computation, p.269-277, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143327]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
lattice reduction, lll, schnorr's algorithm, slide reduction, transference reduction.