International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 10, No. 9, 8 Sep. 2018
Cover page and Table of Contents: PDF (size: 1504KB)
Using Progressive Success Probabilities for Sound-pruned Enumerations in BKZ Algorithm
Full Text (PDF, 1504KB), PP.10-24
Views: 0 Downloads: 0
Author(s)
Index Terms
Lattice reduction, BKZ 2.0, Progressive success probabilities, Sound pruning, Extreme pruning, Parallelization
Abstract
We introduce a new technique for BKZ reduction, which incorporated four improvements of BKZ 2.0 (including: sound pruning, preprocessing of local blocks, shorter enumeration radius and early-abortion). This algorithm is designed based on five claims which be verified strongly in experimental results. The main idea is that, similar to progressive BKZ which using decrement of enumeration cost after each sequence incremental reduction to augment the block size, we use the decrement of enumeration cost after each round of our algorithm to augment the success probability of bounding function. Also we discussed parallelization considerations in our technique.
Cite This Paper
Gholam Reza Moghissi, Ali Payandeh, "Using Progressive Success Probabilities for Sound-pruned Enumerations in BKZ Algorithm", International Journal of Computer Network and Information Security(IJCNIS), Vol.10, No.9, pp.10-24, 2018. DOI:10.5815/ijcnis.2018.09.02
Reference
[1]Ajtai, M., “Generating hard instances of lattice problems”, In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1–32. Dept. Math., Seconda Univ. Napoli, Caserta (2004). Preliminary version in STOC 1996.
[2]Lenstra, Arjen Klaas, Hendrik Willem Lenstra, and László Lovász, “Factoring polynomials with rational coefficients”, Mathematische Annalen 261, no. 4,515-534, 1982.
[3]Schnorr, C.P., “A hierarchy of polynomial time lattice basis reduction algorithms”, Theoretical Computer Science, 53(2-3):201–224, 1987.
[4]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, pp. 1-20. Springer Berlin Heidelberg, 2011.
[5]N. Gama, P. Q. Nguyen, and O. Regev, “Lattice enumeration using extreme pruning”, In Proc. EUROCRYPT ’10, volume 6110 of LNCS. Springer, 2010.
[6]Daniele Micciancio, Oded Regev, “Lattice-based cryptography”, In Post-quantum cryptography, pp. 147-191, Springer Berlin Heidelberg, 2009.
[7]Aono, Yoshinori, 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, pp. 789-819. Springer, Berlin, Heidelberg, 2016.
[8]Gama, N., and Nguyen, P.Q., “Finding short lattice vectors within Mordell’s inequality”, In Proc. 40th ACM Symp. on Theory of Computing (STOC), pages 207–216, 2008.
[9]C. P. Schnorr, M. Euchner, “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems”, Math. Programming, 66:181–199, 1994.
[10]C.-P. Schnorr and H. H. Horner, “Attacking the Chor-Rivest cryptosystem by improved lattice reduction”, In Proc. of Eurocrypt ’95, volume 921 of LNCS, Springer, 1995.
[11]Michael Walter, “Lattice point enumeration on block reduced bases”, In International Conference on Information Theoretic Security, pp. 269-282, Springer International Publishing, 2015.
[12]G. Hanrot, X. Pujol, D. Stehl′e, “Terminating BKZ”, Cryptology ePrint Archive, Report 2011/198, 2011.
[13]V. Shoup, Number Theory C++ Library (NTL), Available at http://www.shoup.net/ntl/.
[14]Nicolas Gama, Phong Q. Nguyen, “Predicting lattice reduction”, In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ’08, volume 4965 of LNCS, pages 31–51, Springer Berlin Heidelberg, April 13, 2008.
[15]Haque, M., Mohammad Obaidur Rahman, and Josef Pieprzyk. "Analysing progressive-BKZ lattice reduction algorithm." Proc. NCICIT 13 (2013): 73-80.
[16]J. Buchmann, C. Ludwig, “Practical lattice basis sampling reduction”, ANTS 2006, LNCS, vol. 4076, pp. 222–237, 2006.
[17]J.H. van de Pol, “Lattice-based cryptography”, Eindhoven University of Technology, Department of Mathematics and Computer Science, July 18, 2011.
[18]Hermans Jens, et al, “Shortest Lattice Vector Enumeration on Graphics Cards”, SHARCS’09 Special-purpose Hardware for Attacking Cryptographic Systems, August 19, 2009.
[19]Dagdelen, ?zgür, and Michael Schneider, “Parallel enumeration of shortest lattice vectors”, In European Conference on Parallel Processing, pp. 211-222, Springer Berlin Heidelberg, 2010.
[20]Michael Schneider, “Computing Shortest Lattice Vectors on Special Hardware”, Department of computer science, Technical Universit¨at Darmstadt, Dissertation for Earning Doctor rerum naturalium (Dr. rer. Nat.), 2011.
[21]Fabio Correia, Artur Mariano, Alberto Proenca, Christian Bischof and Erik Agrell, “Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP”, In 24th Euromicro International Conference on Parallel, Distributed and Network-based Processing, 2016.
[22]Kuo, Po-Chun, Michael Schneider, ?zgür Dagdelen, Jan Reichelt, Johannes Buchmann, Chen-Mou Cheng, and Bo-Yin Yang, “Extreme Enumeration on GPU and in Clouds”, In International Workshop on Cryptographic Hardware and Embedded Systems, pp. 176-191, Springer Berlin Heidelberg, 2011.
[23]Victor Shoup, “NTL vs FLINT”, URL: http://www.shoup.net/ntl/benchmarks.pdf, June 7, 2016.
[24]Daniel Goldstein, Andrew Mayer, “On the equidistribution of Hecke points”, In Forum Mathematicum, vol. 15, no. 2, pp. 165-190, Berlin, January 1, 2003.
[25]R. Lindner, M. Ruckert, “TU Darmstadt lattice challenge”, URL: www.latticechallenge.org.
[26]Buchmann J, Lindner R, Rückert M, “Explicit hard instances of the shortest vector problem”, In Post-Quantum Cryptography, Springer Berlin Heidelberg, pp. 79-94, October 17, 2008.
[27]GitHub hosting service, fplll library project. https://github.com/fplll/, accessed 2016.6.30.