Design of an Accurate BKZ Simulation

Moghissi, Gholam Reza; Payandeh, Ali

doi:10.22042/isecure.2025.440859.1086

Design of an Accurate BKZ Simulation

Document Type : Research Article

Authors

Gholam Reza Moghissi

Ali Payandeh

Department of ICT, Malek-Ashtar University of Technology, Tehran, Iran

https://doi.org/10.22042/isecure.2025.440859.1086

Abstract

The main role of BKZ simulations focuses on showing the behavior of BKZ algorithm for high block sizes, therefore current lattice security analysis (e.g., bit-security estimations and selection of efficient/secure parameter set for current LWE/NTRU-based schemes) needs to these simulations. This paper claims that current BKZ simulations are not necessarily accurate enough for exact lattice security analysis, so for first time, this study introduces two provable tools of “Emulation of updating GSO norms/coefficients” and “Emulation of LLL function” to be used in designing an accurate BKZ simulation. In fact, this paper proves that for a typical SVP solver “Z” (e.g., GNR-enumeration, Sieving, discrete pruning, etc.), if there is a simulation of “Z_emulate” which provably emulates the behaviour of practical running of “Z”, then Our BKZ Simulation by using “emulate_SVPSolver”=“Z_emulate” can provably emulates BKZ algorithm using SVP solver “Z”! Our BKZ Simulation solves different problems and weaknesses in former BKZ simulations. Our tests show that, altogether the shape of GSO norms ‖b_i^* ‖^2, root-Hermite factor of basis, estimated total cost and running time in “Experimental Running of Original BKZ algorithm” are more close to the corresponding test results in “Our BKZ Simulation”, than to the test results in “Chen-Nguyen’s BKZ-simulation”, “BKZ-Simulation by Shi Bai & et al” and some other BKZ models and approximations. Moreover, wrong strategy of updating GSO norms/coefficients in Chen-Nguyen’s BKZ-simulation leads to many GSO violation errors in lattice blocks, while our test results verify that whole these errors would be eliminated automatically in Our BKZ Simulation.

Keywords

Provable Emulation

Gram-Schmidt Orthogonalization (GSO)

Updating GSO Norms

Updating GSO Coefficients

LLL function

GNR enumeration

[1] Anyu Wang, Dianyan Xiao, and Yang Yu. Lattice-based cryptosystems in standardisation processes: A survey. IET Information Security, 17(2):227–243, 2023.
[2] Yuanmi Chen and Phong Q Nguyen. Bkz 2.0: Better lattice security estimates. In International Conference on the Theory and Application of Cryptology and Information Security, pages 1–20. Springer, 2011.
[3] Yoshinori Aono, Yuntao Wang, Takuya Hayashi, and Tsuyoshi Takagi. Improved progressive bkz algorithms and their precise cost estimation by sharp simulator. In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35, pages 789–819. Springer, 2016.
[4] Jianwei Li and Phong Q Nguyen. A complete analysis of the bkz lattice reduction algorithm. Cryptology ePrint Archive, 2020.
[5] Shi Bai, Damien Stehlé, and Weiqiang Wen. Measuring, simulating and exploiting the head concavity phenomenon in bkz. In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I 24, pages 369–404. Springer, 2018.
[6] Tanja Lange Daniel J. Bernstein, Chitchanok Chuengsatiansup and Christine van Vredendaal. "ntru prime". Technical report, National Institute of Standards and Technology, 2017. URL https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions. Submission at Round 1.
[7] Jeff Hoffstein, Jill Pipher, John M Schanck, Joseph H Silverman, William Whyte, and Zhenfei Zhang. Choosing parameters for ntruencrypt. In Cryptographers’ Track at the RSA Conference, pages 3–18. Springer, 2017.
[8] Eamonn W Postlethwaite and Fernando Virdia. On the success probability of solving unique svp via bkz. In IACR International Conference on Public-Key Cryptography, pages 68–98. Springer, 2021.
[9] Yuntao Wang, Yoshinori Aono, and Tsuyoshi Takagi. Hardness evaluation for search lwe problem using progressive bkz simulator. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 101(12):2162–2170, 2018.
[10] Joop van de Pol and Nigel P Smart. Estimating key sizes for high dimensional lattice-based systems. In IMA International Conference on Cryptography and Coding, pages 290–303. Springer, 2013.
[11] Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. Lwe with side information: attacks and concrete security estimation. In Annual International Cryptology Conference, pages 329–358. Springer, 2020.
[12] Martin R Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen. Faster enumeration-based lattice reduction: root hermite factor time. In Annual International Cryptology Conference, pages 186–212. Springer,
2020.
[13] Martin R Albrecht, Shi Bai, Jianwei Li, and Joe Rowell. Lattice reduction with approximate enumeration oracles: practical algorithms and concrete performance. In Annual International Cryptology Conference, pages 732–759. Springer, 2021.
[14] Qian Guo and Thomas Johansson. Faster dual lattice attacks for solving lwe with applications to crystals. In Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part IV 27, pages 33–62. Springer, 2021.
[15] Leizhang Wang, Wenwen Xia, Geng Wang, Baocang Wang, and Dawu Gu. Improved pump and jump bkz by sharp simulator. Cryptology ePrint Archive, 2022.
[16] Leizhang Wang, Yuntao Wang, and Baocang Wang. A trade-off svp-solving strategy based on a sharper pnj-bkz simulator. In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pages 664–677, 2023.
[17] Wenwen Xia, Leizhang Wang, Dawu Gu, Baocang Wang, et al. Improved progressive bkz with lattice sieving and a two-step mode for solving usvp. Cryptology ePrint Archive, 2022.
[18] Ziyu Zhao and Jintai Ding. Several improvements on bkz algorithm. Cryptology ePrint Archive, 2022.
[19] Zishen Zhao and Guangwu Xu. On the measurement and simulation of the bkz behavior for q-ary lattices. In International Conference on Information Security and Cryptology, pages 463–482. Springer, 2022.
[20] Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015.
[21] M. R. Albrecht and et al. Estimate all the {LWE, NTRU} schemes! online version. URL https://estimate-all-the-lwe-ntru-
schemes.github.io/docs/. Accessed: 2024-8-12.
[22] 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! In Security and Cryptography for Networks: 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings 11, pages 351–367. Springer, 2018.
[23] Erdem Alkim, Paulo SLM Barreto, Nina Bindel, Juliane Krämer, Patrick Longa, and Jefferson E Ricardini. The lattice-based digital signature scheme qtesla. In International Conference on Applied Cryptography and Network Security, pages 441–460. Springer, 2020.
[24] Javad Sharafi and Hassan Daghigh. A ring-lwe-based digital signature inspired by lindner–peikert scheme. Journal of Mathematical Cryptology, 16(1):205–214, 2022.
[25] D.J. Bernstein and et al. "ntru prime". Technical report, National Institute of Standards and Technology, 2020. URL https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. Submission at Round 3.
[26] Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M.Schanck, Gregor Seiler, and Damien Stehlé. "crystals-kyber". Technical report, National Institute of Standards and Technology, 2020. URL https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. Submission at Round 3.
[27] Chitchanok Chuengsatiansup, Thomas Prest, Damien Stehlé, Alexandre Wallet, and Keita Xagawa. Modfalcon: Compact signatures based on module-ntru lattices. In Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, pages 853–866, 2020.
[28] Lyubashevsky and et al. "d.s.s.: Crystalsdilithium". Technical report, National Institute of Standards and Technology, 2020. URL https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. Submission at Round 3.
[29] AR Payandeh and GR Moghissi. Revised estimations for cost and success probability of gnrenumeration. Journal of Electrical and Computer Engineering Innovations (JECEI), 11(2): 459–480, 2023.
[30] Gholam Reza Moghissi and Ali Payandeh. Optimal bounding function for gnr-enumeration. International Journal of Mathematical Sciences and Computing (IJMSC), 8(1):1–17, 2022.
[31] Gholam Reza Moghissi and Ali Payandeh. Better sampling method of enumeration solution for bkz-simulation. ISeCure, 13(2), 2021.
[32] Gholam Reza Moghissi and Ali Payandeh. Revised method for sampling coefficient vector of gnr-enumeration solution. Int. J. Math. Sci.Comput.(IJMSC), 8(3):1–20, 2022.
[33] Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, and Amir Hassani Karbasi. Eeh: Aggh-like public key cryptosystem over the eisenstein integers using polynomial representations. ISeCure, 7(2), 2015.
[34] Nicolas Gama, Phong Q Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29, pages 257–278. Springer, 2010.
[35] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-quantum cryptography, pages 147–191. Springer, 2009.
[36] Gholam Reza Moghissi and Ali Payandeh. Design of optimal progressive bkz with increasing success-probabilities and increasing block-sizes. Journal of Computing and Security, 9(2):65–93, 2022.
[37] Claus Peter Schnorr. Lattice reduction by random sampling and birthday methods. In STACS 2003: 20th Annual Symposium on Theoretical Aspects of Computer Science Berlin, Germany, February 27–March 1, 2003 Proceedings
20, pages 145–156. Springer, 2003.
[38] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. 1982.
[39] Yuanmi Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomor-phe. PhD thesis, Paris 7, 2013.
[40] Johannes Buchmann and Christoph Ludwig. Practical lattice basis sampling reduction. In International Algorithmic Number Theory Symposium, pages 222–237. Springer, 2006.
[41] V. Shoup, “NTL: a library for doing number theory”. Online. Available at: http://www.shoup.net/ntl/. Accessed:2024-8-12.
[42] SVP Challenge. Online. Available at: https://www.latticechallenge.org/svp-challenge/index.php. Accessed: 2024-8-12.
[43] Daniel Goldstein and Andrew Mayer. On the equidistribution of hecke points. 2003.
[44] GitHub hosting service, “fplll library project”. Online. Available at: https://github.com/fplll/fplll. Accessed: 2024-8-12.
[45] Yoshinori Aono and Phong Q Nguyen. Random sampling revisited: lattice enumeration with discrete pruning. In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part II 36, pages 65–102. Springer, 2017.
[46] Luan Luan, Chunxiang Gu, Yonghui Zheng, and Yanan Shi. Lattice enumeration with discrete pruning: Improvements, cost estimation and optimal parameters. Mathematics, 11(3):766, 2023.
[47] Léo Ducas. Shortest vector from lattice sieving: a few dimensions for free. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 125–145. Springer, 2018.
[48] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms,
pages 10–24. SIAM, 2016.
[49] Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, and Yang Yu. Orthogonalized lattice enumeration for solving svp. Science China Information Sciences, 61:1–15, 2018.
[50] Gholam Reza Moghissi and Ali Payandeh. A parallel evolutionary search for shortest vector problem. International Journal of Information Technology and Computer Science, 2019.
[51] Luan Luan, Chunxiang Gu, and Yonghui Zheng. A genetic algorithm with restart strategy for solving approximate shortest vector problem. In 2020 12th International Conference on Advanced Computational Intelligence (ICACI), pages 243–250. IEEE, 2020.
[52] Joop van de Pol. Lattice-based cryptography. Eindhoven University of Technology, Department of Mathematics and Computer Science, 2011.
[53] Gholam Reza Moghissi and Ali Payandeh. Using progressive success probabilities for sound-pruned enumerations in bkz algorithm. International Journal of Computer Network and Information Security, 11(9):10, 2018.
[54] Gholam Reza Moghissi and Ali Payandeh. Rejecting claimed speedup of 2β/2 in extreme pruning and revising bkz 2.0 for better speedup. Journal of Computing and Security, 8(1):65–91, 2021.
[55] Nariaki TATEIWA. Development and Numerical Experiments of Massively Parallel Framework and Software for Shortest Vector Problem. PhD thesis, Graduate School of Mathematics, KYUSHU UNIVERSITY. January 17, 2022.
[56] Gholam Reza Moghissi and Ali Payandeh. A software technique to speed up bkz implementations. In 3rd International Conference on Electrical Engineering, 2018. URL https://civilica.com/doc/831793.
[57] Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against ntru. In Advances in Cryptology-CRYPTO 2007: 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007. Proceedings 27, pages 150–169. Springer, 2007.