Abstract
Lattice basis reduction is a mandatory tool to solve lattice problems such as the shortest vector problem (SVP), whose hardness assures the security of lattice-based cryptography. The most famous reduction is the celebrated algorithm by Lenstra-Lenstra–Lovász (LLL), and the block Korkine–Zolotarev (BKZ) is its blockwise generalization. At present, BKZ and its variants such as BKZ 2.0 are a de facto standard reduction algorithm to estimate the security level of lattice-based cryptosystems. Recently, DeepBKZ was proposed as a mathematical improvement of BKZ, in which LLL with deep insertions (DeepLLL) is called as a subroutine alternative to LLL. In this paper, we develop a new self-dual variant of DeepBKZ to obtain a reduced basis. Different from conventional self-dual algorithms, we select suitable free dimensions to reduce primal and dual lattice bases in our variant. We also report experimental results to compare our self-dual DeepBKZ with primal BKZ and DeepBKZ for several random lattice bases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albrecht M, Ducas L, Herold G, Kirshanova E, Postlethwaite EW, Stevens M (2019) The general sieve kernel and new records in lattice reduction. IACR ePrint 2019/089
Albrecht MR, Curtis BR, Deo A, Davidson A, Player R, Postlethwaite EW, Virdia F, Wunderer T (2018) Estimate all the LWE, NTRU schemes! In: Security and cryptography for networks (SCN 2018). Lecture Notes in Computer Science, vol 11035, pp 351–367
Aono Y, Wang Y, Hayashi T, Takagi T (2016) Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Advances in Cryptology–EUROCRYPT 2016. Lecture Notes in Computer Science, vol 9665. Springer, pp. 789–819. progressive BKZ library is available from https://www2.nict.go.jp/security/pbkzcode/
Bremner MR (2011) Lattice basis reduction: an introduction to the LLL algorithm and its applications. CRC Press
Chen Y (2013) Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. PhD thesis, Paris 7
Chen Y, Nguyen PQ (2011) BKZ 2.0: Better lattice security estimates. In: Advances in Cryptology–ASIACRYPT 2011. Lecture Notes in Computer Science, vol 7073. Springer, pp 1–20
Darmstadt T. SVP challenge, available at https://www.latticechallenge.org/svp-challenge/
Galbraith SD (2012) Mathematics of public key cryptography. Cambridge University Press
Gama N, Nguyen PQ (2008) Finding short lattice vectors within Mordell’s inequality. In: Symposium on theory of computing (STOC 2008). ACM, pp 207–216
Gama N, Nguyen PQ (2008) Predicting lattice reduction. In: Advances in cryptology–EUROCRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, pp 31–51
Gama N, Nguyen PQ, Regev O (2010) Lattice enumeration using extreme pruning. In: Advances in cryptology–EUROCRYPT 2010. Lecture Notes in Computer Science, vol 6110. Springer, pp 257–278
Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math Oper Rese 12(3):415–440
Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math Ann 261(4):515–534
Micciancio D, Walter M (2016) Practical, predictable lattice basis reduction. In: Advances in cryptology–EUROCRYPT 2016. Lecture Notes in Computer Science, vol 9665. Springer, pp. 820–849
Nguyen PQ (2009) Hermite’s constant and lattice algorithms. In: The LLL algorithm. Springer, pp 19–69
Schnorr CP (1987) A hierarchy of polynomial time lattice basis reduction algorithms. Theoret Comput Sci 53(2–3):201–224
Schnorr CP (1992). Block Korkin-Zolotarev bases and successive minima. International Computer Science Institute
Schnorr CP (2003) Lattice reduction by random sampling and birthday methods. In: Symposium on theoretical aspects of computer science (STACS 2003). Lecture Notes in Computer Science, vol 2607. Springer, pp. 145–156
Schnorr CP, Euchner M (1994) Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math Program 66:181–199
Shoup V NTL: a library for doing number theory. https://www.shoup.net/ntl/
The FPLLL development team: fplll, a lattice reduction library (2016), https://github.com/fplll/fplll
The FPyLLL development team: fpylll, a lattice reduction library (2018), https://github.com/fplll/fpylll
The National Institute of Standards and Technology (NIST): Post-quantum cryptography, https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
Yamaguchi J, Yasuda M (2017) Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications. In: Number-theoretic methods in cryptology (NuTMiC 2017). Lecture Notes in Computer Science, vol 10737. Springer, pp. 142–160
Yasuda M (2018) Self-dual DeepBKZ for finding short lattice vectors. Presented at MathCrypt 2018 (to appear in a MathCrypt 2018 special issue of Journal of Mathematical Cryptology)
Yasuda M, Yamaguchi J (2019) A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths. Designs, Codes and Cryptography, First Online
Yasuda M, Yamaguchi J, Ooka M, Nakamura S (2018) 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, vol 10831. Springer, pp 162–182
Yu Y, Ducas L (2017) Second order statistical behavior of LLL and BKZ. In: Selected areas in cryptography (SAC 2017). Lecture Notes in Computer Science, vol 10719. Springer, pp. 3–22
Acknowledgments
This work was supported by JSPS KAKENHI Grant Number 16H02830.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Nakamura, S., Ikematsu, Y., Yasuda, M. (2021). Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions. In: Giri, D., Buyya, R., Ponnusamy, S., De, D., Adamatzky, A., Abawajy, J.H. (eds) Proceedings of the Sixth International Conference on Mathematics and Computing. Advances in Intelligent Systems and Computing, vol 1262. Springer, Singapore. https://doi.org/10.1007/978-981-15-8061-1_30
Download citation
DOI: https://doi.org/10.1007/978-981-15-8061-1_30
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-8060-4
Online ISBN: 978-981-15-8061-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)