skip to main content
research-article

Low-dimensional lattice basis reduction revisited

Authors Info & Claims
Published:06 November 2009Publication History
Skip Abstract Section

Abstract

Lattice reduction is a geometric generalization of the problem of computing greatest common divisors. Most of the interesting algorithmic problems related to lattice reduction are NP-hard as the lattice dimension increases. This article deals with the low-dimensional case. We study a greedy lattice basis reduction algorithm for the Euclidean norm, which is arguably the most natural lattice basis reduction algorithm because it is a straightforward generalization of an old two-dimensional algorithm of Lagrange, usually known as Gauss' algorithm, and which is very similar to Euclid's gcd algorithm. Our results are twofold. From a mathematical point of view, we show that up to dimension four, the output of the greedy algorithm is optimal: The output basis reaches all the successive minima of the lattice. However, as soon as the lattice dimension is strictly higher than four, the output basis may be arbitrarily bad as it may not even reach the first minimum. More importantly, from a computational point of view, we show that up to dimension four, the bit-complexity of the greedy algorithm is quadratic without fast integer arithmetic, just like Euclid's gcd algorithm. This was already proved by Semaev up to dimension three using rather technical means, but it was previously unknown whether or not the algorithm was still polynomial in dimension four. We propose two different analyzes: a global approach based on the geometry of the current basis when the length decrease stalls, and a local approach showing directly that a significant length decrease must occur every O(1) consecutive steps. Our analyzes simplify Semaev's analysis in dimensions two and three, and unify the cases of dimensions two to four. Although the global approach is much simpler, we also present the local approach because it gives further information on the behavior of the algorithm.

References

  1. Ajtai, M. 1996. Generating hard instances of lattice problems (extended abstract). In Proceedings of the 28th Symposium on the Theory of Computing (STOC'96). ACM Press, 99--108. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Ajtai, M. 1998. The shortest vector problem in l<sub>2</sub> is NP-hard for randomized reductions (extended abstract). In Proceedings of the 30th Symposium on the Theory of Computing (STOC'98). ACM Press, 284--293. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Akhavi, A. 2000. Worst-Case complexity of the optimal LLL algorithm. In Proceedings of the Latin American Theoretical Informatics (LATIN'00). Lecture Notes in Computer Science, vol. 1776. Springer-Verlag, 355--366. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Akhavi, A., and Moreira dos Santos, C. 2004. Another view of the Gaussian algorithm. In Proceedings of the Latin American Theoretical Informatics (LATIN'04). Lecture Notes in Computer Science, vol. 2976. Springer-Verlag, 474--487.Google ScholarGoogle Scholar
  5. Babai, L. 1986. On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6, 1--13. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Cassels, J. W. S. 1971. An Introduction to the Geometry of Numbers, 2nd Ed. Springer-Verlag.Google ScholarGoogle Scholar
  7. Conway, J. H., and Sloane, N. J. A. 1988. Sphere Packings, Lattices and Groups. Springer-Verlag. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Delone, B. N., and Sandakova, N. N. 1961. Theory of stereohedra. Trudy Math. Instit. Steklov 64, 28--51.Google ScholarGoogle Scholar
  9. Eisenbrand, F. and Rote, G. 2001. Fast reduction of ternary quadratic forms. In Proceedings of the Cryptography and Lattices Conference (CALC'01). Lecture Notes in Computer Science, vol. 2146. Springer-Verlag, 32--44. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Gama, N., and Nguyen, P. Q. 2008. Finding short lattice vectors within Mordell's inequality. In Proceedigns of the 40th ACM Symposium on the Theory of Computing (STOC'06). ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Gauss, C. F. 1801. Disquisitiones Arithmeticæ. Springer-Verlag.Google ScholarGoogle Scholar
  12. Helfrich, B. 1985. Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoretical Comput. Sci. 41, 125--139. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Hermite, C. 1850. Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre. J. für die reine und angewandte Mathematik 40, 279--290.Google ScholarGoogle Scholar
  14. Hermite, C. 1905. &OElig;uvres. Gauthiers-Villars.Google ScholarGoogle Scholar
  15. Kaib, M., and Schnorr, C. P. 1996. The generalized Gauss reduction algorithm. J. Algor. 21, 3, 565--578. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Kannan, R. 1983. Improved algorithms for integer programming and related lattice problems. In Proceedings of the 15th Symposium on the Theory of Computing (STOC'83). ACM Press, 99--108. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Korkine, A., and Zolotarev, G. 1873. Sur les formes quadratiques. Mathematische Annalen 6, 336--389.Google ScholarGoogle ScholarCross RefCross Ref
  18. Lagarias, J. C. 1980. Worst-Case complexity bounds for algorithms in the theory of integral quadratic forms. J. Algor. 1, 142--186.Google ScholarGoogle ScholarCross RefCross Ref
  19. Lagarias, J. C., Lenstra, W. H., and Schnorr, C. P. 1990. Korkine-Zolotarev bases and successive minimal of a lattice and its reciprocal lattice. Combinatorica 10, 333--348.Google ScholarGoogle ScholarCross RefCross Ref
  20. Lagrange, J. L. 1773. Recherches d'arithmétique. Nouveaux Mémoires de l'Académie de Berlin.Google ScholarGoogle Scholar
  21. Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515--534.Google ScholarGoogle ScholarCross RefCross Ref
  22. Martinet, J. 2002. Perfect Lattices in Euclidean Spaces. Springer-Verlag.Google ScholarGoogle Scholar
  23. Micciancio, D., and Goldwasser, S. 2002. Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Minkowski, H. 1896. Geometrie der Zahlen. Teubner-Verlag.Google ScholarGoogle Scholar
  25. Nguyen, P. Q., and Stehlé, D. 2004. Low-Dimensional lattice basis reduction revisited (extended abstract). In Proceedings of the 6th Algorithmic Number Theory Symposium (ANTSVI). Lecture Notes in Computer Science, vol. 3076. Springer-Verlag, 338--357.Google ScholarGoogle Scholar
  26. Nguyen, P. Q., and Stehlé, D. 2005. Floating-Point LLL revisited. In Proceedings of Eurocrypt. Lecture Notes in Computer Science, vol. 3494. Springer-Verlag, 215--233. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Nguyen, P. Q., and Stern, J. 2001. The two faces of lattices in cryptology. In Proceedings of the Cryptography and Lattices Conference (CALC'01). Lecture Notes in Computer Science, vol. 2146. Springer-Verlag, 146--180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Ryskov, S. S. 1972. On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables. Soviet Mathematics Doklady 13, 1676--1679.Google ScholarGoogle Scholar
  29. Schnorr, C. P. 1987. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Comput. Sci. 53, 201--224.Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. Schnorr, C. P., and Euchner, M. 1994. Lattice basis reduct: Improved practical algorithms and solving subset sum problems. Math. Program. 66, 181--199. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Schnorr, C. P., and Hörner, H. H. 1995. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In Proceedings of Eurocrypt. Lecture Notes in Computer Science, vol. 921. Springer-Verlag, 1--12. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Schönhage, A., and Strassen, V. 1971. Schnelle Multiplikation grosser Zahlen. Comput. 7, 281--292.Google ScholarGoogle ScholarCross RefCross Ref
  33. Semaev, I. 2001. A 3-dimensional lattice reduction algorithm. In Proceedings of the Cryptography and Lattices Conference (CALC'01). Lecture Notes in Computer Science, vol. 2146. Springer-Verlag, 181--193. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. Siegel, C. L. 1989. Lectures on the Geometry of Numbers. Springer-Verlag.Google ScholarGoogle Scholar
  35. Stogrin, M. I. 1977. Regular Dirichlet-Voronoï partitions for the second triclinic group. American Mathematical Society. English translation of the proceedings of the Steklov Institute of Mathematics, Number 123 (1973).Google ScholarGoogle Scholar
  36. Tammela, P. P. 1973. On the reduction theory of positive quadratic forms. Soviet Mathematics Doklady 14, 651--655.Google ScholarGoogle Scholar
  37. Vallée, B. 1986. Une approche géométrique de la réduction des réseaux en petite dimension. Ph.D. thesis, Université de Caen.Google ScholarGoogle Scholar
  38. Vallée, B. 1991. Gauss' algorithm revisited. J. Algor. 12, 556--572. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. Voronoï, G. 1908. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. J. für die Reine und angewandte Mathematik 134, 198--287.Google ScholarGoogle Scholar
  40. van der Waerden, B. L. 1956. Die Reduktionstheorie der positiven quadratischen Formen. Acta Mathematica 96, 265--309.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Low-dimensional lattice basis reduction revisited

          Recommendations

          Reviews

          Bruce E. Litow

          This paper gives an extremely detailed account of a greedy lattice reduction algorithm and its complexity analysis up to dimension four. It also studies failure of the algorithm starting at dimension five. For a general perspective on the closest vector problem (CVP) and shortest vector problem (SVP) associated to lattices, see Khot's paper [1]. Nguyen and Stehlé work with Minkowski-reduced lattices. A d -dimensional lattice L is generated by a spanning set of vectors b 1 , ... , b d (the lattice basis) in E d and L is the set of all vectors Σ d i =1 a i · b i , where the a i are integers. A lattice basis for L is said to be Minkowski reduced if each b i has minimal norm among all vectors b in L such that b 1, ... , b i -1, b can be extended to a basis for L . A critical set of lattice parameters that are directly connected to SVP is λ1( L ), ... ,λ d ( L ), where each λ i ( L ) is the radius of the smallest ball centered at the origin containing i linearly independent lattice vectors. This definition makes sense because of the discrete nature of lattices. The λ( L ) figure prominently in the complexity analysis of the authors' greedy basis reduction algorithm. The principal result of the paper is Theorem 4.2.1. There are some assumptions about precomputed inputs. The authors mention only that | b 1| = ... = | b d | is assumed. Their greedy algorithm uses O (__?__log | b d | · (1 + log | b d | - log λ1( L ))__?__) bit operations and is shown to be correct for d = 4. The O notation is independent of d , although the authors show that correctness is lost for d > 4. In a very careful but clear analysis, it is shown that the total cost of bit operations at each step of the algorithm is linear in log | b d |, yielding an overall quadratic bit complexity for the algorithm. There are numerous interesting linear algebra lemmas in the paper and a clever application of low-dimensional Voronoï tessellations to the stepwise analysis. Some of this material may be of use to computational geometers. The detail of the paper is both its strength and its weakness. An exhaustive study of Minkowski reduction is carried out through dimension four, but the complications of the approach seem to become overwhelming as the dimension grows. Online Computing Reviews Service

          Access critical reviews of Computing literature here

          Become a reviewer for Computing Reviews.

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Algorithms
            ACM Transactions on Algorithms  Volume 5, Issue 4
            October 2009
            281 pages
            ISSN:1549-6325
            EISSN:1549-6333
            DOI:10.1145/1597036
            Issue’s Table of Contents

            Copyright © 2009 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 6 November 2009
            • Accepted: 1 January 2009
            • Revised: 1 October 2008
            • Received: 1 August 2006
            Published in talg Volume 5, Issue 4

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article
            • Research
            • Refereed

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader