February  2020, 14(1): 137-159. doi: 10.3934/amc.2020011

Certified lattice reduction

1. 

Sorbonne Université, LIP 6, CNRS UMR 7606, Paris, France

2. 

Chaire de Cryptologie de la Fondation SU, Sorbonne Université, Institut de Mathématiques de Jussieu–Paris Rive Gauche, CNRS, INRIA, Univ Paris Diderot., Campus Pierre et Marie Curie, F-75005, Paris, France

Received  April 2019 Published  August 2019

Fund Project: This work has been supported in part by the European Union as H2020 Programme under grant agreement number ERC-669891

Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducing integral lattice basis. In particular, its floating-point variants---where the rational arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic---are now the fastest known. However, the systematic study of the reduction theory of real quadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In this work, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields.

Citation: Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011
References:
[1]

K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux, 16 (2004), 19-63. doi: 10.5802/jtnb.433. Google Scholar

[2]

J.-F. Biasse and C. Fieker, Improved techniques for computing the ideal class group and a system of fundamental units in number fields, The Open Book Series, 1 (2013), 113-133. doi: 10.2140/obs.2013.1.113. Google Scholar

[3]

J. Buchmann, Reducing lattice bases by means of approximations, Algorithmic Number Theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci., Springer, Berlin, 877 (1994), 160–168. doi: 10.1007/3-540-58691-1_54. Google Scholar

[4]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag New York, Inc., New York, NY, USA, 1993. doi: 10.1007/978-3-662-02945-9. Google Scholar

[5]

B. M. M. de Weger, Solving exponential Diophantine equations using lattice basis reduction algorithms, J. Number theory, 26 (1987), 325-367. doi: 10.1016/0022-314X(87)90088-6. Google Scholar

[6]

N. D. Elkies, Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction, Algorithmic Number Theory: 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000, Proceedings, 1838 (2000), 33–63. doi: 10.1007/10722028_2. Google Scholar

[7]

A. Gélin and A. Joux, Reducing number field defining polynomials: An application to class group computations, LMS J. Comput. Math., 19 (2016), 315-331. doi: 10.1112/S1461157016000255. Google Scholar

[8]

X. Gourdon, Combinatoire, algorithmique et géométrie des polynomes, PhD thesis, 27–49.Google Scholar

[9]

G. HavasB. S. Majewski and K. R. Matthews, Extended GCD and Hermite normal form algorithms via lattice basis reduction, Experimental Mathematics, 7 (1998), 125-136. doi: 10.1080/10586458.1998.10504362. Google Scholar

[10]

G. Jäger, Reduction of Smith normal form transformation matrices, Computing, 74 (2005), 377-388. doi: 10.1007/s00607-004-0104-0. Google Scholar

[11]

L. Jaulin, M. Kieffer, O. Didrit and É. Walter, Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer Verlag, 2001. doi: 10.1007/978-1-4471-0249-6. Google Scholar

[12]

E. Kaltofen, On the complexity of finding short vectors in integer lattices, in Computer Algebra, EUROCAL '83, European Computer Algebra Conference (ed. J. A. van Hulzen), Lecture Notes in Computer Science, Springer, 162 (1983), 236–244. doi: 10.1007/3-540-12868-9_107. Google Scholar

[13]

S. Kim and A. Venkatesh, The behavior of random reduced bases, International Mathematics Research Notices, 2018 (2018), 6442-6480. doi: 10.1093/imrn/rnx074. Google Scholar

[14]

A. K. LenstraH. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar

[15]

H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), 538-548. doi: 10.1287/moor.8.4.538. Google Scholar

[16]

H. W. Lenstra Jr. and A. Silverberg, Lattices with symmetry, Journal of Cryptology, 30 (2017), 760-804. doi: 10.1007/s00145-016-9235-7. Google Scholar

[17]

L. Lovász and H. E. Scarf, The generalized basis reduction algorithm, Math. Oper. Res., 17 (1992), 751-764. doi: 10.1287/moor.17.3.751. Google Scholar

[18]

R. E. Moore, Interval Arithmetic and Automatic Error Analysis in Digital Computing, PhD Thesis, Stanford, 1962.Google Scholar

[19]

R. E. Moore, Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, 2. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. Google Scholar

[20]

P. Q. Nguyen, Hermite's Constant and Lattice Algorithms, in The LLL algorithm (eds. P. Q. Nguyen and B. Vallée), Springer, 2010.Google Scholar

[21]

P. Q. Nguyen and D. Stehlé, An LLL algorithm with quadratic complexity, SIAM J. of Computing, 39 (2009), 874-903. doi: 10.1137/070705702. Google Scholar

[22]

G. Pataki and M. Tural, On Sublattice Determinants in Reduced Bases, 2008.Google Scholar

[23]

M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation, 4 (1987), 123-127. doi: 10.1016/S0747-7171(87)80061-5. Google Scholar

[24] H. Ratschek and J. Rokne, New Computer Methods for Global Optimization, Halsted Press, New York, NY, USA, 1988. Google Scholar
[25]

C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., 53 (1987), 201-224. doi: 10.1016/0304-3975(87)90064-8. Google Scholar

[26]

C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms, 9 (1988), 47-62. doi: 10.1016/0196-6774(88)90004-1. Google Scholar

[27]

C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 66 (1994), 181-199. doi: 10.1007/BF01581144. Google Scholar

[28]

T. Sunaga, Theory of an interval algebra and its application to numerical analysis, Japan J. Indust. Appl. Math., 26 (2009), 125-143. doi: 10.1007/BF03186528. Google Scholar

[29]

FPLLL development team, Fplll, a lattice reduction library, 2016, Available at URL https://github.com/fplll/fplll.Google Scholar

[30]

G. Villard, Certification of the $QR$ factor $R$ and of lattice basis reducedness, ISSAC 2007, ACM, New York, (2007), 361–368, . doi: 10.1145/1277548.1277597. Google Scholar

[31]

R. C. Young, The algebra of many-values quantities, Math. Ann., 104 (1931), 260-290. doi: 10.1007/BF01457934. Google Scholar

show all references

References:
[1]

K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux, 16 (2004), 19-63. doi: 10.5802/jtnb.433. Google Scholar

[2]

J.-F. Biasse and C. Fieker, Improved techniques for computing the ideal class group and a system of fundamental units in number fields, The Open Book Series, 1 (2013), 113-133. doi: 10.2140/obs.2013.1.113. Google Scholar

[3]

J. Buchmann, Reducing lattice bases by means of approximations, Algorithmic Number Theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci., Springer, Berlin, 877 (1994), 160–168. doi: 10.1007/3-540-58691-1_54. Google Scholar

[4]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag New York, Inc., New York, NY, USA, 1993. doi: 10.1007/978-3-662-02945-9. Google Scholar

[5]

B. M. M. de Weger, Solving exponential Diophantine equations using lattice basis reduction algorithms, J. Number theory, 26 (1987), 325-367. doi: 10.1016/0022-314X(87)90088-6. Google Scholar

[6]

N. D. Elkies, Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction, Algorithmic Number Theory: 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000, Proceedings, 1838 (2000), 33–63. doi: 10.1007/10722028_2. Google Scholar

[7]

A. Gélin and A. Joux, Reducing number field defining polynomials: An application to class group computations, LMS J. Comput. Math., 19 (2016), 315-331. doi: 10.1112/S1461157016000255. Google Scholar

[8]

X. Gourdon, Combinatoire, algorithmique et géométrie des polynomes, PhD thesis, 27–49.Google Scholar

[9]

G. HavasB. S. Majewski and K. R. Matthews, Extended GCD and Hermite normal form algorithms via lattice basis reduction, Experimental Mathematics, 7 (1998), 125-136. doi: 10.1080/10586458.1998.10504362. Google Scholar

[10]

G. Jäger, Reduction of Smith normal form transformation matrices, Computing, 74 (2005), 377-388. doi: 10.1007/s00607-004-0104-0. Google Scholar

[11]

L. Jaulin, M. Kieffer, O. Didrit and É. Walter, Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer Verlag, 2001. doi: 10.1007/978-1-4471-0249-6. Google Scholar

[12]

E. Kaltofen, On the complexity of finding short vectors in integer lattices, in Computer Algebra, EUROCAL '83, European Computer Algebra Conference (ed. J. A. van Hulzen), Lecture Notes in Computer Science, Springer, 162 (1983), 236–244. doi: 10.1007/3-540-12868-9_107. Google Scholar

[13]

S. Kim and A. Venkatesh, The behavior of random reduced bases, International Mathematics Research Notices, 2018 (2018), 6442-6480. doi: 10.1093/imrn/rnx074. Google Scholar

[14]

A. K. LenstraH. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar

[15]

H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), 538-548. doi: 10.1287/moor.8.4.538. Google Scholar

[16]

H. W. Lenstra Jr. and A. Silverberg, Lattices with symmetry, Journal of Cryptology, 30 (2017), 760-804. doi: 10.1007/s00145-016-9235-7. Google Scholar

[17]

L. Lovász and H. E. Scarf, The generalized basis reduction algorithm, Math. Oper. Res., 17 (1992), 751-764. doi: 10.1287/moor.17.3.751. Google Scholar

[18]

R. E. Moore, Interval Arithmetic and Automatic Error Analysis in Digital Computing, PhD Thesis, Stanford, 1962.Google Scholar

[19]

R. E. Moore, Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, 2. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. Google Scholar

[20]

P. Q. Nguyen, Hermite's Constant and Lattice Algorithms, in The LLL algorithm (eds. P. Q. Nguyen and B. Vallée), Springer, 2010.Google Scholar

[21]

P. Q. Nguyen and D. Stehlé, An LLL algorithm with quadratic complexity, SIAM J. of Computing, 39 (2009), 874-903. doi: 10.1137/070705702. Google Scholar

[22]

G. Pataki and M. Tural, On Sublattice Determinants in Reduced Bases, 2008.Google Scholar

[23]

M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation, 4 (1987), 123-127. doi: 10.1016/S0747-7171(87)80061-5. Google Scholar

[24] H. Ratschek and J. Rokne, New Computer Methods for Global Optimization, Halsted Press, New York, NY, USA, 1988. Google Scholar
[25]

C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., 53 (1987), 201-224. doi: 10.1016/0304-3975(87)90064-8. Google Scholar

[26]

C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms, 9 (1988), 47-62. doi: 10.1016/0196-6774(88)90004-1. Google Scholar

[27]

C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 66 (1994), 181-199. doi: 10.1007/BF01581144. Google Scholar

[28]

T. Sunaga, Theory of an interval algebra and its application to numerical analysis, Japan J. Indust. Appl. Math., 26 (2009), 125-143. doi: 10.1007/BF03186528. Google Scholar

[29]

FPLLL development team, Fplll, a lattice reduction library, 2016, Available at URL https://github.com/fplll/fplll.Google Scholar

[30]

G. Villard, Certification of the $QR$ factor $R$ and of lattice basis reducedness, ISSAC 2007, ACM, New York, (2007), 361–368, . doi: 10.1145/1277548.1277597. Google Scholar

[31]

R. C. Young, The algebra of many-values quantities, Math. Ann., 104 (1931), 260-290. doi: 10.1007/BF01457934. Google Scholar

Figure 1.  Basic arithmetic operators in Interval Arithmetic
[1]

Henrique Bursztyn, Alejandro Cabrera. Symmetries and reduction of multiplicative 2-forms. Journal of Geometric Mechanics, 2012, 4 (2) : 111-127. doi: 10.3934/jgm.2012.4.111

[2]

Andrejs Reinfelds, Klara Janglajew. Reduction principle in the theory of stability of difference equations. Conference Publications, 2007, 2007 (Special) : 864-874. doi: 10.3934/proc.2007.2007.864

[3]

David Blázquez-Sanz, Juan J. Morales-Ruiz. Lie's reduction method and differential Galois theory in the complex analytic context. Discrete & Continuous Dynamical Systems - A, 2012, 32 (2) : 353-379. doi: 10.3934/dcds.2012.32.353

[4]

L. Búa, T. Mestdag, M. Salgado. Symmetry reduction, integrability and reconstruction in $k$-symplectic field theory. Journal of Geometric Mechanics, 2015, 7 (4) : 395-429. doi: 10.3934/jgm.2015.7.395

[5]

Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465

[6]

Hiroaki Yoshimura, Jerrold E. Marsden. Dirac cotangent bundle reduction. Journal of Geometric Mechanics, 2009, 1 (1) : 87-158. doi: 10.3934/jgm.2009.1.87

[7]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297

[8]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[9]

Jean-François Babadjian, Francesca Prinari, Elvira Zappale. Dimensional reduction for supremal functionals. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1503-1535. doi: 10.3934/dcds.2012.32.1503

[10]

Martins Bruveris, David C. P. Ellis, Darryl D. Holm, François Gay-Balmaz. Un-reduction. Journal of Geometric Mechanics, 2011, 3 (4) : 363-387. doi: 10.3934/jgm.2011.3.363

[11]

Katarzyna Grabowska, Paweƚ Urbański. Geometry of Routh reduction. Journal of Geometric Mechanics, 2019, 11 (1) : 23-44. doi: 10.3934/jgm.2019002

[12]

Joshua Cape, Hans-Christian Herbig, Christopher Seaton. Symplectic reduction at zero angular momentum. Journal of Geometric Mechanics, 2016, 8 (1) : 13-34. doi: 10.3934/jgm.2016.8.13

[13]

Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008

[14]

Sujay Jayakar, Robert S. Strichartz. Average number of lattice points in a disk. Communications on Pure & Applied Analysis, 2016, 15 (1) : 1-8. doi: 10.3934/cpaa.2016.15.1

[15]

Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015

[16]

Andrei Korobeinikov, Aleksei Archibasov, Vladimir Sobolev. Order reduction for an RNA virus evolution model. Mathematical Biosciences & Engineering, 2015, 12 (5) : 1007-1016. doi: 10.3934/mbe.2015.12.1007

[17]

Sergio Grillo, Marcela Zuccalli. Variational reduction of Lagrangian systems with general constraints. Journal of Geometric Mechanics, 2012, 4 (1) : 49-88. doi: 10.3934/jgm.2012.4.49

[18]

Marco Castrillón López, Pablo M. Chacón, Pedro L. García. Lagrange-Poincaré reduction in affine principal bundles. Journal of Geometric Mechanics, 2013, 5 (4) : 399-414. doi: 10.3934/jgm.2013.5.399

[19]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of discrete mechanical systems by stages. Journal of Geometric Mechanics, 2016, 8 (1) : 35-70. doi: 10.3934/jgm.2016.8.35

[20]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems. Journal of Geometric Mechanics, 2010, 2 (1) : 69-111. doi: 10.3934/jgm.2010.2.69

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (14)
  • HTML views (72)
  • Cited by (0)

Other articles
by authors

[Back to Top]