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.
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- Babai, L. 1986. On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6, 1--13. Google ScholarDigital Library
- Cassels, J. W. S. 1971. An Introduction to the Geometry of Numbers, 2nd Ed. Springer-Verlag.Google Scholar
- Conway, J. H., and Sloane, N. J. A. 1988. Sphere Packings, Lattices and Groups. Springer-Verlag. Google ScholarDigital Library
- Delone, B. N., and Sandakova, N. N. 1961. Theory of stereohedra. Trudy Math. Instit. Steklov 64, 28--51.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Gauss, C. F. 1801. Disquisitiones Arithmeticæ. Springer-Verlag.Google Scholar
- Helfrich, B. 1985. Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoretical Comput. Sci. 41, 125--139. Google ScholarDigital Library
- 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 Scholar
- Hermite, C. 1905. Œuvres. Gauthiers-Villars.Google Scholar
- Kaib, M., and Schnorr, C. P. 1996. The generalized Gauss reduction algorithm. J. Algor. 21, 3, 565--578. Google ScholarDigital Library
- 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 ScholarDigital Library
- Korkine, A., and Zolotarev, G. 1873. Sur les formes quadratiques. Mathematische Annalen 6, 336--389.Google ScholarCross Ref
- Lagarias, J. C. 1980. Worst-Case complexity bounds for algorithms in the theory of integral quadratic forms. J. Algor. 1, 142--186.Google ScholarCross Ref
- 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 ScholarCross Ref
- Lagrange, J. L. 1773. Recherches d'arithmétique. Nouveaux Mémoires de l'Académie de Berlin.Google Scholar
- Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515--534.Google ScholarCross Ref
- Martinet, J. 2002. Perfect Lattices in Euclidean Spaces. Springer-Verlag.Google Scholar
- Micciancio, D., and Goldwasser, S. 2002. Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Press. Google ScholarDigital Library
- Minkowski, H. 1896. Geometrie der Zahlen. Teubner-Verlag.Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Ryskov, S. S. 1972. On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables. Soviet Mathematics Doklady 13, 1676--1679.Google Scholar
- Schnorr, C. P. 1987. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Comput. Sci. 53, 201--224.Google ScholarDigital Library
- Schnorr, C. P., and Euchner, M. 1994. Lattice basis reduct: Improved practical algorithms and solving subset sum problems. Math. Program. 66, 181--199. Google ScholarDigital Library
- 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 ScholarDigital Library
- Schönhage, A., and Strassen, V. 1971. Schnelle Multiplikation grosser Zahlen. Comput. 7, 281--292.Google ScholarCross Ref
- 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 ScholarDigital Library
- Siegel, C. L. 1989. Lectures on the Geometry of Numbers. Springer-Verlag.Google Scholar
- 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 Scholar
- Tammela, P. P. 1973. On the reduction theory of positive quadratic forms. Soviet Mathematics Doklady 14, 651--655.Google Scholar
- 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 Scholar
- Vallée, B. 1991. Gauss' algorithm revisited. J. Algor. 12, 556--572. Google ScholarDigital Library
- 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 Scholar
- van der Waerden, B. L. 1956. Die Reduktionstheorie der positiven quadratischen Formen. Acta Mathematica 96, 265--309.Google ScholarCross Ref
Index Terms
Low-dimensional lattice basis reduction revisited
Recommendations
A Lattice Reduction Algorithm Based on Sublattice BKZ
Provable and Practical SecurityAbstractWe present m-SubBKZ reduction algorithm that outputs a reduced lattice basis, containing a vector shorter than the original BKZ. The work is based on the properties of sublattices and the Gaussian Heuristic of the full lattice and sublattices. By ...
Recursive lattice reduction
SCN'10: Proceedings of the 7th international conference on Security and cryptography for networksLattice reduction is known to be a very powerful tool in modern cryptanalysis. In the literature, there are many lattice reduction algorithms that have been proposed with various time complexity (from quadratic to subexponential). These algorithms can ...
A complexity analysis of a Jacobi method for lattice basis reduction
C3S2E '12: Proceedings of the Fifth International C* Conference on Computer Science and Software EngineeringThe famous LLL algorithm is the first polynomial time lattice reduction algorithm which is widely used in many applications. In this paper, we present a novel weak Quasi-Jacobi lattice basis reduction algorithm based on a polynomial time algorithm, ...
Comments