Design of Optimal Progressive BKZ with Increasing Success-Probabilities and Increasing Block-Sizes

Document Type : Research Article

Authors

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

Abstract

Former studies on progressive-BKZ almost focus on increasing block sizes. Our work in IJCNIS 9.9, 2018, introduces a new version of progressive-BKZ based on increasing success probabilities, while its results are not sufficiently hopeful! This paper introduces two algorithms of “BKZ with optimal progressive block sizes” and “BKZ with optimal progressive success probabilities”, while their time-complexities are proved to be optimal. However these two proposed algorithms are designed to solve exact-SVP for an input basis, they can be used as an SVP-solver in the body of another BKZ algorithm for practical attacks! Also, our proposed algorithms can be used as reasonable representatives of two approaches of “increasing block sizes” and “increasing success probabilities” in the progressive-BKZ family to be compared with each other for the first time. For dimension n≥90, BKZ with optimal progressive success probabilities shows better runtime than corresponding instances of BKZ with optimal progressive block sizes, so that for Gentry-Halevi’s main lattice challenges, these speedups include: “2^14.1 times for Toy challenge of n=512”, “2^67.2 times for Small challenge of n=2048”, “2^235.5 times for Medium challenge of n=8192” and “2^1207.7 times for large challenge of n=32768”. Also, the time cost of BKZ with optimal progressive success probabilities and optimal progressive block sizes as two exact-SVP solvers are compared with some main claimants of exact-SVP solvers such as sieve algorithm, extreme-pruned enumeration, full-enumeration, and so on, for the dimensions of 100≤β≤240, and our results show hopeful time cost against these claimants. Moreover, two Cost-Models are approximated for these two optimal progressive BKZ.

Keywords

Main Subjects

References

[1] Y. Chen and P. Q. Nguyen. BKZ 2.0: Better lattice security estimates. In Advances in Cryptology--ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17, pages 1--20. Springer, 2021. [ bib | DOI ]
[2] G. R. Moghissi and A. Payandeh. Using Progressive Success Probabilities for Sound-pruned Enumerations in BKZ Algorithm. International Journal of Computer Network and Information Security, 11(9):10--24, 2018. [ bib | DOI ]
[3] Y. Aono, Y. Wang, T. Hayashi, and T. 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. [ bib | DOI ]
[4] M. Haque and M. O. Rahman. Analyzing progressive-bkz lattice reduction algorithm. International Journal of Computer Network and Information Security, 11(1):40--46, 2019. [ bib | DOI ]
[5] P. Schmidt. Fully homomorphic encryption: Overview and cryptanalysis. Dortmund: Technische Universität Dortmund, 2011. [ bib | DOI ]
[6] N. Gama, P. Q. Nguyen, and O. 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. [ bib | DOI ]
[7] S. Bai, D. Stehlé, and W. 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. [ bib | DOI ]
[8] C. P. 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. [ bib | DOI ]
[9] J. Buchmann and C. Ludwig. Practical lattice basis sampling reduction. In Algorithmic Number Theory: 7th International Symposium, ANTS-VII, Berlin, Germany, July 23-28, 2006. Proceedings 7, pages 222--237. Springer, 2006. [ bib | DOI ]
[10] P. Q. Nguyen and V. Brigitte. The LLL Algorithm: survey and application. Springer, 2020. [ bib ]
[11] G. R. Moghissi and A. Payandeh. Better Sampling Method of Enumeration Solution for BKZ-Simulation. ISeCure, 13(2), 2021. [ bib | DOI ]
[12] G. R. Moghissi and A. 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. [ bib | DOI ]
[13] G. R. Moghissi and A. Payandeh. Optimal bounding function for GNR-enumeration. International Journal of Mathematical Sciences and Computing (IJMSC), 8(1):1--17, 2022. [ bib | DOI ]
[14] G. R. Moghissi and A. Payandeh. A parallel evolutionary search for shortest vector problem. International Journal of Information Technology and Computer Science, 2019. [ bib | DOI ]
[15] C. A. Rogers. The number of lattice points in a set. Proceedings of the London Mathematical Society, 3(2):305--320, 1956. [ bib | DOI ]
[16] M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. W. Postlethwaite, F. Virdia, and T. 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. [ bib | DOI ]
[17] E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe. Post-quantum key exchange-A New Hope. In USENIX security symposium, 2016. [ bib | DOI ]
[18] A. Becker, L. Ducas, N. Gama, and T. 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. [ bib | DOI ]
[19] T. Laarhoven. Search problems in cryptography: from fingerprinting to lattice sieving. 2016. [ bib | DOI ]
[20] M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169--203, 2015. [ bib | DOI ]
[21] P. Q. Nguyen. Hermite’s constant and lattice algorithms. In The LLL Algorithm: Survey and Applications, pages 19--69. Springer, 2009. [ bib ]
[22] R. Lindner and C. Peikert. Better key sizes (and attacks) for LWE-based encryption. In Topics in Cryptology--CT-RSA 2011: The Cryptographers’ Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings, pages 319--339. Springer, 2011. [ bib | DOI ]
[23] Y. Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. Ph.D. thesis, Paris 7, 2013. [ bib ]
[24] Y. Chen and P. Q. Nguyen. BKZ 2.0: Better lattice security estimates. In Advances in Cryptology--ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17, pages 1--20. Springer, 2011. [ bib | DOI ]
[25] J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte, and Z. Zhang. Choosing parameters for NTRUEncrypt. In Topics in Cryptology--CT-RSA 2017: The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14--17, 2017, Proceedings, pages 3--10. Springer, 2017. [ bib | DOI ]
[26] V. Shoup. NTL: A Library for doing Number Theory. https://libntl.org/, Date Accessed: 2022. [ bib ]
[27] TU Darmstadt Lattice Challenge. SVP Challenge. https://www.latticechallenge.org/svp-challenge/, Date Accessed: 2022. [ bib ]
Journal of Computing and Security
Volume 9, Issue 2
July 2022
Pages 65-93

Files

History

  • Receive Date: 02 October 2021
  • Revise Date: 27 November 2022
  • Accept Date: 12 December 2022

Share

How to cite

Statistics