Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup

Document Type : Research Article

Authors

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

Abstract

 
BKZ 2.0 algorithm is one of the claimant lattice reduction algorithms which incorporates extreme pruning as its main phase. The non-extreme pruning and extreme pruning in the original paper by Gamma-Nguyen-Regev (in 2010) respectively are claimed to reach the maximum speedup of 2^(β/4) and 2^(β/2) over full-enumeration. For 37≤β, this paper verifies the claimed speedup of 2^(β/4) by an optimal non-extreme pruned enumeration, while for a practical block size of 100≤β≤250, the upper-bound for speedup of extreme-pruned enumeration when blocks are preprocessed by BKZ with enumeration (as SVP-solver) is estimated from 2^(β/6.6) to 2^(β/4.4), and when blocks are preprocessed by BKZ with sieving is estimated from 2^(β/9.8) to 2^(β/3.4) ! By using these upper-bounds for speedup by extreme-pruning, all former security analyses which use the claimed speedup of 2^(β/2), should be revised  (or rejected). Also, this paper proposes a revised version of BKZ 2.0, so that for a practical block size of 100≤β≤250 and an infinite number of rounds N≈∞, the lower-bound of its speedup over BKZ 2.0 is estimated by a factor of ρ_0 in range of 2^12≤ρ_0≤2^15.5 when blocks are preprocessed by BKZ with enumeration, and also lower-bound of its speedup is estimated in the range of 0≤ρ_0≤2^20.5 when blocks are preprocessed by BKZ with sieving. Moreover, for a finite number of rounds N, speedup of our revised BKZ 2.0 over original BKZ 2.0 can be estimated by O(min⁡(N,ρ_0 ) ). 

Keywords

References

[1] D. Micciancio and O. Regev. Lattice-based cryptography. In Post-quantum cryptography, pages 147--191. Springer, 2009. [ bib | DOI ]
[2] J. van de Pol. Lattice-based cryptography. Eindhoven University of Technology, Department of Mathematics and Computer Science, 2011. [ bib | DOI ]
[3] A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische annalen, 261:515–534, 1982. [ bib | DOI ]
[4] C. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical computer science, 53(2-3):201--224, 1987. [ bib | DOI ]
[5] J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A ring-based public key cryptosystem. In International Algorithmic Number Theory Symposium, pages 267--288. Springer, 1998. [ bib | DOI ]
[6] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSIGN: Digital signatures using the NTRU lattice. In Cryptographers’ track at the RSA conference, pages 122--140. Springer, 2003. [ bib | DOI ]
[7] J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, and W. Whyte. Practical signatures from the partial Fourier recovery problem. In International Conference on Applied Cryptography and Network Security, pages 476--493. Springer, 2014. [ bib | DOI ]
[8] N. Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In Annual International Cryptology Conference, pages 150--169. Springer, 2007. [ bib | DOI ]
[9] 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 International Conference on Security and Cryptography for Networks, pages 351--367. Springer, 2018. [ bib | DOI ]
[10] Y. Chen and P. 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. [ bib | DOI ]
[11] N. Gama, P. Q. Nguyen, and O. Regev. Lattice enumeration using extreme pruning. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 257--278. Springer, 2011. [ bib | DOI ]
[12] A. Mariano, T. Laarhoven, F. Correia, M. Rodrigues, and G. Falcao. A practical view of the state-of-the-art of lattice-based cryptanalysis. IEEE Access, 5:24184 -- 24202, 2017. [ bib | DOI ]
[13] Y. Aono, Y. Wang, T. Hayashi, and T. Takagi. Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 789--819. Springer, 2016. [ bib | DOI ]
[14] J. Buchmann and C. Ludwig. Practical Lattice Basis Sampling Reduction. In International Algorithmic Number Theory Symposium, pages 222--237. Springer, 2006. [ bib | DOI ]
[15] N. Gama and P. Q. Nguyen. Predicting Lattice Reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 31--51. Springer, 2008. [ bib | DOI ]
[16] C. P. Schnorr. Lattice Reduction by Random Sampling and Birthday Methods. In Annual Symposium on Theoretical Aspects of Computer Science, pages 145--156. Springer, 2003. [ bib | DOI ]
[17] C. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66(1):181–199, 1994. [ bib | DOI ]
[18] C. Schnorr and H. H. Hörner. Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 1--12. Springer, 1995. [ bib | DOI ]
[19] V. Shoup. Ntl: A library for doing number theory. https://libntl.org/, Date Accessed: 2021. [ bib ]
[20] Y. Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. PhD thesis, Paris 7, 2013. [ bib ]
[21] D. Micciancio and M. Walter. Practical, Predictable Lattice Basis Reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 820--849. Springer, 2016. [ bib | DOI ]
[22] C. A. Rogers. The Number of Lattice Points in a Set. London Mathematical Society, 3(3):305–320, 1956. [ bib | DOI ]
[23] M. Walter. Lattice point enumeration on block reduced bases. In International Conference on Information Theoretic Security, pages 269--282. Springer, 2015. [ bib | DOI ]
[24] 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 ]
[25] J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte, and Z. Zhang. Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive: Report 2015/708, 2015. [ bib | DOI ]
[26] 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 ]
[27] G. Hanrot, X. Pujol, and D. Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. In Annual Cryptology Conference, pages 447--464. Springer, 2011. [ bib | DOI ]
[28] P. Kuo, M. Schneider, Ö. Dagdelen, J. Reichelt, J. Buchmann, C. Cheng, and B. Yang. Extreme Enumeration on GPU and in Clouds. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 176--191. Springer, 2011. [ bib | DOI ]
[29] F. Correia, A. Mariano, A. Proenca, C. Bischof, and E. Agrell. Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 596--603. IEEE, 2016. [ bib | DOI ]
[30] G. R. Moghissi and A. Payandeh. Improvement in results of parallelization approaches of lattice enumeration function on CPU and GPU. In 4th National Conference on technology in Electrical and Computer Engineering. CIVILICA, 2018. [ bib | DOI ]
[31] G. R. Moghissi and A. Payandeh. A software technique to speed up BKZ implementations. In 3rd International Conference on Electrical Engineering, Tehran, New Technologies Associations. CIVILICA, 2018. [ bib | DOI ]
Journal of Computing and Security
Volume 8, Issue 1 - Serial Number 1
January 2021
Pages 65-91

Files

History

  • Receive Date: 20 January 2020
  • Revise Date: 31 May 2021
  • Accept Date: 14 July 2021

Share

How to cite

Statistics