×

An experimental comparison of some LLL-type lattice basis reduction algorithms. (English) Zbl 1392.11097

Summary: In this paper we experimentally compare the performance of the \(L^2\) lattice basis reduction algorithm, whose importance recently became evident, with our own Gram-based lattice basis reduction algorithm, which is a variant of the Schnorr-Euchner algorithm. We conclude with observations about the algorithms under investigation for lattice basis dimensions up to the theoretical limit. We also reexamine the notion of “buffered transformations” and its impact on performance of lattice basis reduction algorithms. We experimentally compare four different algorithms directly in the Sage Mathematics Software: our own algorithm, the \(L^2\) algorithm and “buffered” versions of them resulting in a total of four algorithms.

MSC:

11Y16 Number-theoretic algorithms; complexity
68W30 Symbolic computation and algebraic computation
94A60 Cryptography
68P25 Data encryption (aspects in computer science)

Software:

SageMath; Python; NTRU
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the 29th symposium on the theory of computing (STOC), pp. 284-293, ACM Press (1997) · Zbl 0962.68055
[2] Backes, W., Wetzel, S.: An efficient LLL Gram using buffered transformations. In: Proceedings of computer algebra in scientific computing, LNCS vol. 4770, pp 31-44 (2007) · Zbl 1141.68667
[3] Backes, W; Wetzel, S, Heuristics on lattice basis in practice, J. Exp. Algorithmics, 7, 1-21, (2002) · Zbl 1086.68588 · doi:10.1145/944618.944619
[4] Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer Verlag, Berlin-Heidelberg (2009) · Zbl 1155.81007
[5] Bremner, M.R.: Lattice Basis Reduction, An Introduction to the LLL Algorithm and its Applications. CRC Press, Boca Raton (2012) · Zbl 1237.68007
[6] Finch, C.: Sage Beginner’s Guide. Packt Publishing, Birmingham (2011)
[7] Hecker, C.: Automatische Parallelisierung und Parallelle Gitterbasisreduction, Ph.D. Thesis, Universität des Saarlandes, Saarbrücken (1994)
[8] Generation of Unimodular Matrices with Bounded Elements, http://math.stackexchange.com/questions/336829/generation-of-unimodular-matrices-with-bounded-elements, (2014). Accessed 2014
[9] Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Proceedings of crypto 1997, LNCS, vol. 1294, pp. 112-131. Springer-Verlag (1997) · Zbl 0889.94011
[10] Hoffstein, J., Pipher, J., Silverman, J.H.: An Introduction to Mathematical Cryptography. Springer-Verlag, New York (2008) · Zbl 1160.94001
[11] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring based public key cryptosystem. In: Proceedings of the 3rd algorithmic number theory aymposium (ANTS III), LNCS, vol. 1423, pp. 267-288, Springer-Verlag (1998) · Zbl 1067.94538
[12] IEEE 754 Floating Point Standard, http://steve.hollasch.net/cgindex/coding/ieeefloat.html, (2014). Accessed 2014 · Zbl 1103.68997
[13] Johnson, D, A theoretician’s guide to the experimental analysis of algorithms, Discret. Math. Theor. Comput. Sci., 59, 215-250, (2001) · Zbl 1103.68997
[14] Lenstra, A; Lenstra, H; Lovász, L, Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534, (1982) · Zbl 0488.12001 · doi:10.1007/BF01457454
[15] McGeoch, C.C.: A Guide to Experimental Algorithmics. Cambridge University Press, Cambridge (2012)
[16] Nguyen, PQ; Stehlé, D, An LLL algorithm with quadratic complexity, SIAM J. Comput., 39, 874-903, (2009) · Zbl 1214.11139 · doi:10.1137/070705702
[17] Nguyen, P.Q., Stehlé, D.: Floating-point LLL revisited, In: Cramer, R.J.F. (ed.), EUROCRYPT 2005, LNCS vol. 3494, pp 215-233, Springer, Heidelberg (2005) · Zbl 1137.94353
[18] Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm. Survey and Applications. Springer Verlag, Heidelberg (2010) · Zbl 1179.11003
[19] Novocin, A., Stehlé, D., Villard, G.: An LLL-reduction algorithm with quasi-linear time complexity, In: Proceedings of the 43rd annual ACM symposium on theory of computing (2011) · Zbl 1288.68294
[20] http://www.python.org, Python home page, (2014). Accessed 2014
[21] Schnorr, C., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. In: Budach, L. (ed.) FCT 1991, LNCS, vol. 529, pp. 68-85. Springer, Heidelberg (1991) · Zbl 0925.11049
[22] Stein W.A., et al.: Sage Mathematics Software (Version 5.13), The Sage Development Team, 2013, http://www.sagemath.org, (2013)
[23] Wetzel, S.: Lattice basis reduction algorithms and their applications. PhD thesis, Universität des Saarlandes (1998) · Zbl 1086.68588
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.