International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 11, No. 1, 8 Jan. 2019
Cover page and Table of Contents: PDF (size: 872KB)
Analyzing Progressive-BKZ Lattice Reduction Algorithm
Full Text (PDF, 872KB), PP.40-46
Views: 0 Downloads: 0
Author(s)
Index Terms
Cryptosystems, Lattice reduction, BKZ, Gram-Schmidt vectors, SWIFFT
Abstract
BKZ and its variants are considered as the most efficient lattice reduction algorithms compensating both the quality and runtime. Progressive approach (gradually increasing block size) of this algorithm has been attempted in several works for better performance but actual analysis of this approach has never been reported. In this paper, we plot experimental evidence of its complexity over the direct approach. We see that a considerable time saving can be achieved if we use the output basis of the immediately reduced block as the input basis of the current block (with increased block size) successively. Then, we attempt to ?nd pseudo-collision in SWIFFT hash function and show that a different set of parameters produces a special shape of Gram-Schmidt norms other than the predicted Geometric Series Assumptions (GSA) which the experiment suggests being more efficient.
Cite This Paper
Md. Mokammel Haque, Mohammad Obaidur Rahman, "Analyzing Progressive-BKZ Lattice Reduction Algorithm", International Journal of Computer Network and Information Security(IJCNIS), Vol.11, No.1, pp.40-46, 2019. DOI:10.5815/ijcnis.2019.01.04
Reference
[1]V. Lyubashevsky, D. Micciancio, C. Peikert and A. Rosen. SWIFFT: A Modest Proposal for FFT Hashing. In Fast Software Encryption (FSE) 2008, LNCS, pp. 54-72. Springer-Verlag, 2008.
[2]A. K. Lenstra, H. W. Lenstra, Jr., and L. Lova′sz. Factoring polynomials with rational coef?cients. Math. Ann., 261(4): 515-534, 1982.
[3]C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2-3): 201-224, 1987.
[4]N. Gama and P. Q. Nguyen. Predicting lattice reduction. In EUROCRYPT, 2008, LNCS 4965, pp. 31-51. Springer, 2008.
[5]C.-P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming, 66:181-199, 1994.
[6]V. Shoup. NTL: A library for doing number theory. Available at http://www.shoup.net/ntl/.
[7]R. Kannan. Improved algorithms for integer programming and related lattice problems. In Proc. of 15th ACM Symp. on Theory of Computing (STOC), pp. 193-206. ACM, 1983.
[8]G. Hanrot, D. Stehle′. Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm. In CRYPTO 2007, LNCS 4622, pp. 170-186, 2007.
[9]N. Gama, P. Q. Nguyen, O. Regev. Lattice enumeration using Extreme Pruning. In EUROCRYPT, 2010, LNCS, Springer-Verlag, 2010.
[10]J. Buchmann and R. Lindner. Secure Parameters for SWIFFT. In INDOCRYPT’09, pp. 1-17, 2009.
[11]R. Lindner and C. Peikert. Better key sizes (and attacks) for LWE-based encryption. In Proc. of the 11th international conference on Topics in cryptology, CT-RSA’11, pp. 319-339, Springer-Verlag, 2011.
[12]Y. Chen and P. Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In ASIACRYPT’11, LNCS 7073, pp. 1-20. IACR, 2011.
[13]P. Q. Nguyen and V. Brigitte. The LLL Algorithm: survey and application. Chapter-2 (Hermite’s Constant and Lattice Algorithms). ISBN 978-3-642-02294-4, 2010.
[14]C.-P. Schnorr. Lattice reduction by random sampling and birthday methods. In STACS’03, LNCS, vol. 2607, pp. 145-156. Springer, 2003.
[15]G. Hanrot, X. Pujol and D. Stehle′. Analyzing Blockwise Lattice Algorithms using Dynamical Systems. Accepted to CRYPTO 2011.
[16]C.-P. Schnorr and H. H. Ho¨rner. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In EUROCRYPT95, LNCS 921, pp. 1-12, Springer-Verlag, 1995.
[17]D. Micciancio and O. Regev. Post Quantum Cryptography. Chapter Lattice based Cryptography. Springer-Verlag, 2009.