Self-dual DeepBKZ for finding short lattice vectors. (English) Zbl 1448.94235

Summary: In recent years, the block Korkine-Zolotarev (BKZ) and its variants such as BKZ 2.0 have been used as de facto algorithms to estimate the security of a lattice-based cryptosystem. In 2017 [the author et al., NuTMiC 2017, Lect. Notes Comput. Sci. 10737, 142–160 (2018; Zbl 1423.94115)], DeepBKZ was proposed as a mathematical improvement of BKZ, which calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. DeepBKZ can find a short lattice vector by smaller blocksizes than BKZ. In this paper, we develop a self-dual variant of DeepBKZ, as in the work of D. Micciancio and M. Walter [Eurocrypt 2016, Lect. Notes Comput. Sci. 9665, 820–849 (2016; Zbl 1385.94062)] for self-dual BKZ. Like DeepBKZ, our self-dual DeepBKZ calls both DeepLLL and its dual variant as main subroutines in order to accelerate to find a very short lattice vector. We also report experimental results of DeepBKZ and our self-dual DeepBKZ for random bases on the Darmstadt SVP challenge.


94A60 Cryptography
68P25 Data encryption (aspects in computer science)
68W30 Symbolic computation and algebraic computation


fpLLL; GitHub; NTL; BKZ
Full Text: DOI


[1] Martin R Albrecht, Benjamin R Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W Postlethwaite, Fernando Virdia and Thomas Wunderer, Estimate all the {LWE, NTRU} schemes!, Cryptology ePrint Archive: Report 2018/331 (2018). · Zbl 06957562
[2] Yuanmi Chen, Réduction de réseau et sécurité concrete du chiffrement completement homomorphe, Ph.D. thesis, Paris 7, 2013.
[3] Yuanmi Chen and Phong Q Nguyen, BKZ 2.0: Better lattice security estimates, in: Advances in Cryptology-ASIACRYPT 2011, Lecture Notes in Computer Science 7073, Springer, pp. 1-20, 2011. · Zbl 1227.94037
[4] TU Darmstadt, SVP Challenge, Available at https://www.latticechallenge.org/svp-challenge/, 2018.
[5] The FPLLL development team, fplll, a lattice reduction library, Available at https://github.com/fplll/fplll, 2016.
[6] Nicolas Gama and Phong Q Nguyen, Finding short lattice vectors within mordell’s inequality, in: Proceedings of the fortieth annual ACM symposium on Theory of computing, ACM, pp. 207-216, 2008. · Zbl 1230.11153
[7] Nicolas Gama and Phong Q Nguyen, Predicting lattice reduction, in: Advances in Cryptology-EUROCRYPT 2008, Lecture Notes in Computer Science 4965, Springer, pp. 31-51, 2008. · Zbl 1149.94314
[8] Nicolas Gama, Phong Q Nguyen and Oded Regev, Lattice enumeration using extreme pruning, in: Advances in Cryptology-EUROCRYPT 2010, Lecture Notes in Computer Science 6110, Springer, pp. 257-278, 2010. · Zbl 1280.94056
[9] Guillaume Hanrot, Xavier Pujol and Damien Stehlé, Analyzing blockwise lattice algorithms using dynamical systems, in: Advances in Cryptology-CRYPTO 2011, Lecture Notes in Computer Science 6841, Springer, pp. 447-464, 2011. · Zbl 1287.94072
[10] Arjen Klaas Lenstra, Hendrik Willem Lenstra and László Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen261 (1982), 515-534. · Zbl 0488.12001
[11] Daniele Micciancio and Michael Walter, Practical, predictable lattice basis reduction, in: Advances in Cryptology-EUROCRYPT 2016, Lecture Notes in Computer Science 9665, Springer, pp. 820-849, 2016. · Zbl 1385.94062
[12] Phong Q Nguyen, Hermite’s constant and lattice algorithms, The LLL Algorithm, Springer, 2009, pp. 19-69. · Zbl 1230.11155
[13] The National Institute of Standards and Technology (NIST), Post-Quantum Cryptography Standardization, Available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.
[14] Claus-Peter Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical computer science53 (1987), 201-224. · Zbl 0642.10030
[15] Claus-Peter Schnorr, Block Korkin-Zolotarev bases and successive minima, International Computer Science Institute, 1992.
[16] Claus-Peter Schnorr and Martin Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical programming66 (1994), 181-199. · Zbl 0829.90099
[17] Victor Shoup, NTL: A Library for doing Number Theory, Available at http://www.shoup.net/ntl/.
[18] Junpei Yamaguchi and Masaya Yasuda, Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications, in: International Conference on Number-Theoretic Methods in Cryptology-NuTMiC 2017, Lecture Notes in Computer Science 10737, Springer, pp. 142-160, 2017. · Zbl 1423.94115
[19] Masaya Yasuda, Junpei Yamaguchi, Michiko Ooka and Satoshi Nakamura, Development of a dual version of DeepBKZ and its application to solving the LWE challenge, in: Progress in Cryptology-AFRICACRYPT 2018, Lecture Notes in Computer Science 10831, Springer, pp. 162-182, 2018. · Zbl 1423.94117
[20] Yang Yu and Léo Ducas, Second order statistical behavior of LLL and BKZ, in: Selected Areas in Cryptography-SAC 2017, Lecture Notes in Computer Science 10719, Springer, pp. 3-22, 2017. · Zbl 1384.94111
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.