Document Type : Research Article

Authors

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

Abstract

The exact manner of BKZ algorithm for higher block sizes cannot be studied by practical running, so simulation of BKZ can be used to predict the total cost and output quality of BKZ algorithm. Sampling method of enumeration solution vector v is one of the main components of designing BKZ-simulation and can be divided into two phases: sampling norm of solution vector v and sampling corresponding coefficient vectors. This paper introduces a simple and efficient idea for sampling the norm of enumeration solution v for any success probability of enumeration bounding functions, while to the best of our knowledge, no such sampling method for norm of enumeration solution is proposed in former studies. Next, this paper analyzes the structure and probability distribution of coefficient vectors (corresponding with enumeration solution v), and consequently introduces the sampling methods for these coefficient vectors which are verified by our test results, while no such a deep analysis for sampling coefficient vectors is considered in design of former BKZ-simulations. Moreover, this paper proposes an approximation for cost of enumerations pruned by optimal bounding functions.

Keywords

1] Nicolas Gama, Phong Q Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 257–278. Springer, 2010.
[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] Shi Bai, Damien Stehlé, and Weiqiang Wen. Measuring, simulating and exploiting the head concavity phenomenon in BKZ. In International Conference on the Theory and Application of Cryptology and Information Security, pages 369– 404. Springer, 2018.
[4] Yoshinori Aono, Yuntao Wang, Takuya Hayashi, and Tsuyoshi 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.
[5] 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.
[6] Tancrede Lepoint and Michael Naehrig. A comparison of the homomorphic encryption schemes FV and YASHE. In International Conference on Cryptology in Africa, pages 318–335. Springer, 2014.
[7] Mingjie Liu and Phong Q Nguyen. Solving BDD by enumeration: An update. In Cryptographers’ Track at the RSA Conference, pages 293–309. Springer, 2013.
[8] Yoshinori Aono, Xavier Boyen, Lihua Wang, et al. Key-private proxy re-encryption under LWE. In International Conference on Cryptology in India, pages 1–18. Springer, 2013.
[9] 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 International Conference on Security and Cryptography for Networks, pages 351– 367. Springer, 2018.
[10] Jeff Hoffstein, Jill Pipher, John M Schanck, Joseph H Silverman, and William Whyte. Practical signatures from the partial fourier recovery problem. In International Conference on Applied Cryptography and Network Security, pages 476–493. Springer, 2014.
[11] Yuanmi Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. PhD thesis, Paris 7, 2013.
[12] Daniele Micciancio and Oded Regev. Latticebased cryptography. In Post-quantum cryptography, pages 147–191. Springer, 2009.
[13] Claus Peter Schnorr. Lattice reduction by random sampling and birthday methods. In Annual Symposium on Theoretical Aspects of Computer Science, pages 145–156. Springer, 2003.
[14] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische annalen, 261(ARTICLE):515–534, 1982.
[15] CA Rogers. The number of lattice points in a set. Proceedings of the London Mathematical Society, 3(2):305–320, 1956.
[16] Johannes Buchmann and Christoph Ludwig. Practical lattice basis sampling reduction. In International Algorithmic Number Theory Symposium, pages 222–237. Springer, 2006.
[17] SVP Challenge. Available at: https: //www.latticechallenge.org/svpchallenge/index.php.
[18] Daniel Goldstein and Andrew Mayer. On the equidistribution of Hecke points. In Forum Mathematicum, volume 15, 2003.
[19] Yang Yu and Léo Ducas. Second order statistical behavior of LLL and BKZ. In International Conference on Selected Areas in Cryptography, pages 3–22. Springer, 2017.
[20] Johannes Buchmann, Richard Lindner, and Markus Rückert. Explicit hard instances of the shortest vector problem. In International Workshop on Post-Quantum Cryptography, pages 79– 94. Springer, 2008.
[21] TU Darmstadt lattice challenge. Available at: www.latticechallenge.org.
[22] Yoshinori Aono and Phong Q Nguyên. Random sampling revisited: lattice enumeration with discrete pruning. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 65–102. Springer, 2017.
[23] 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.
[24] Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, and Yang Yu. Orthogonalized lattice enumeration for solving SVP. Science China Information Sciences, 61(3):1–15, 2018.
[25] Gholam Reza Moghissi and Ali Payandeh. A parallel evolutionary search for shortest vector problem. Int. J. Inf. Technol. Comput. Sci.(IJITCS), 11(8):9–19, 2019.
[26] Joop van de Pol. Lattice-based cryptography. Eindhoven University of Technology, Department of Mathematics and Computer Science, 2011.
[27] Johan Ludwig William Valdemar Jensen et al. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta mathematica, 30:175– 193, 1906.