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.

[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.

[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.

[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.

[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.

[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.

[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.

[8]

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

[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.

[10]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[18]

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

[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.

[20]

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

[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.

[22]

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

[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.

[24] H. Ratschek and J. Rokne, New Computer Methods for Global Optimization, Halsted Press, New York, NY, USA, 1988. 
[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.

[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.

[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.

[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.

[29]

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

[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.

[31]

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

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.

[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.

[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.

[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.

[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.

[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.

[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.

[8]

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

[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.

[10]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[18]

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

[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.

[20]

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

[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.

[22]

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

[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.

[24] H. Ratschek and J. Rokne, New Computer Methods for Global Optimization, Halsted Press, New York, NY, USA, 1988. 
[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.

[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.

[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.

[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.

[29]

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

[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.

[31]

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

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 and Continuous Dynamical Systems, 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 and 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]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[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]

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

[15]

Lyudmila Grigoryeva, Juan-Pablo Ortega. Dimension reduction in recurrent networks by canonicalization. Journal of Geometric Mechanics, 2021, 13 (4) : 647-677. doi: 10.3934/jgm.2021028

[16]

Jing Li, Panos Stinis. Model reduction for a power grid model. Journal of Computational Dynamics, 2022, 9 (1) : 1-26. doi: 10.3934/jcd.2021019

[17]

Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129

[18]

Anish Ghosh, Dubi Kelmer. A quantitative Oppenheim theorem for generic ternary quadratic forms. Journal of Modern Dynamics, 2018, 12: 1-8. doi: 10.3934/jmd.2018001

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (449)
  • HTML views (416)
  • Cited by (0)

Other articles
by authors

[Back to Top]