International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 11, No. 8, 8 Aug. 2019
Cover page and Table of Contents: PDF (size: 774KB)
A Parallel Evolutionary Search for Shortest Vector Problem
Full Text (PDF, 774KB), PP.9-19
Views: 0 Downloads: 0
Author(s)
Index Terms
SVP, Lattice reduction, Lattice based cryptography, Evolutionary Search, Genetic Algorithm, Parallelization, Graphic card
Abstract
The hardness assumption of approximate shortest vector problem (SVP) within the polynomial factor in polynomial time reduced to the security of many lattice-based cryptographic primitives, so solving this problem, breaks these primitives. In this paper, we investigate the suitability of combining the best techniques in general search/optimization, lattice theory and parallelization technologies for solving the SVP into a single algorithm. Our proposed algorithm repeats three steps in a loop: an evolutionary search (a parallelized Genetic Algorithm), brute-force of tiny full enumeration (in role of too much local searches with random start points over the lattice vectors) and a single main enumeration. The test results showed that our proposed algorithm is better than LLL reduction and may be worse than the BKZ variants (except some so small block sizes). The main drawback for these test results is the not-sufficient tuning of various parameters for showing the potential strength of our contribution. Therefore, we count the entire main problems and weaknesses in our work for clearer and better results in further studies. Also it is proposed a pure model of Genetic Algorithm with more solid/stable design for SVP problem which can be inspired by future works.
Cite This Paper
Gholam Reza Moghissi, Ali Payandeh, "A Parallel Evolutionary Search for Shortest Vector Problem", International Journal of Information Technology and Computer Science(IJITCS), Vol.11, No.8, pp.9-19, 2019. DOI:10.5815/ijitcs.2019.08.02
Reference
[1]Daniele Micciancio, Oded Regev, “Lattice-based cryptography”, In Post-quantum cryptography, pp. 147-191, Springer Berlin Heidelberg, 2009.
[2]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.
[3]P. V. E. Boas, “Another np-complete problem and the complexity of computing short vector in a lattice”, in Tech. rep 8104, University of Amsterdam, Department of Mathematics, Netherlands, 1981.
[4]M. Ajtai, “The shortest vector problem in l2 is np-hard for randomized reductions”, in STOC 98: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, New York, NY, USA, 1998, pp. 10–19.
[5]D. Micciancio, “The shortest vector in a lattice is hard to approximate to within some constant”, SIAM Journal of Computing, vol. 30(6), pp. 2008–2035, 2001.
[6]Hanrot, Guillaume, Damien Stehlé, “Improved analysis of Kannan’s shortest lattice vector algorithm”, In Annual International Cryptology Conference, pp. 170-186. Springer, Berlin, Heidelberg, 2007.
[7]D. Micciancio, Michael Walter, “Fast lattice point enumeration with minimal overhead”, In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pp. 276-294. Society for Industrial and Applied Mathematics, 2014.
[8]C. P. Schnorr, M. Euchner, “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems”, Math. Programming, 66:181–199, 1994.
[9]N. Gama, P. Q. Nguyen, O. Regev, “Lattice enumeration using extreme pruning”, In Proc. EUROCRYPT ’10, volume 6110 of LNCS. Springer, 2010.
[10]C.-P. Schnorr, H. Horner, “Attacking the Chor-Rivest cryptosystem by improved lattice reduction”, In Proc. of Eurocrypt ’95, volume 921 of LNCS, Springer, 1995.
[11]Yuanmi Chen, 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.
[12]Y. Aono, Y. Wang, T. Hayashi, 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, pp. 789-819. Springer, Berlin, Heidelberg, 2016.
[13]Micciancio, Daniele, Panagiotis Voulgaris, “A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations”, SIAM Journal on Computing 42, no. 3 (2013): 1364-1391.
[14]Aggarwal, Divesh, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz, “Solving the shortest vector problem in 2^n time using discrete Gaussian sampling” In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 733-742. ACM, 2015.
[15]Anja Becker, Leo Ducas, Nicolas Gama, Thijs Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving”, In Robert Krauthgamer, editor, 27th SODA, pages 10-24. ACM-SIAM, January 2016.
[16]Victor Shoup, “NTL vs FLINT”, available at http://www.shoup.net/ntl/benchmarks.pdf.
[17]GitHub hosting service, fplll library project, available at https://github.com/fplll/.
[18]Eiben, Agoston E., James E. Smith, “Introduction to evolutionary computing”, Vol. 53. Heidelberg: springer, 2003.
[19]Shenoy, K. B. A., Somenath Biswas, Piyush P. Kurur, “Metropolis algorithm for solving shortest lattice vector problem (SVP)”, Hybrid Intelligent Systems (HIS), 2011 11th International Conference on. IEEE, 2011.
[20]Oltean, Gabriel, “Fuzzy Techniques in Optimization-Based Analog Design”, WSEAS International Conference, Proceedings. Mathematics and Computers in Science and Engineering. Eds. W. B. Mikhael, et al. No. 10. World Scientific and Engineering Academy and Society, 2008.
[21]Hopfield J., Tank D., “Neural Computation of Decisions in Optimization Problems”, Biological Cybernetics, Vol. 52, pp 141-152, 1985.
[22]Ding D, Zhu G Z, Wang X Y., “A genetic algorithm for searching the shortest lattice vector of SVP challenge”, In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, 2015, 823–830.
[23]Fukase M, Kashiwabara K., “An accelerated algorithm for solving SVP based on statistical analysis”, J Inf Process, 2015, 23: 67–80.
[24]Zhongxiang Zheng, Xiaoyun Wang, Yang Yu, “Orthogonalized lattice enumeration for solving SVP”, Science China Information Sciences 2018.
[25]Aono, Yoshinori, Phong Q. Nguyen, Yixin Shen, “Quantum lattice enumeration and tweaking discrete pruning”, International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2018.
[26]Fabio Correia, Artur Mariano, Alberto Proenca, Christian Bischof, 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.
[27]Kuo, Po-Chun, Michael Schneider, Özgür Dagdelen, Jan Reichelt, Johannes Buchmann, Chen-Mou Cheng, 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.
[28]T Teruya, K Kashiwabara, G Hanaoka, “Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem”, PKC 2018: Public-Key Cryptography – PKC 2018 pp 437-460
[29]“CUDA C Programming Guide”, eBook, NVIDIA Corporation, available at www.nvidia.com, July 19, 2013.
[30]Chris Lomont, “Introduction to x64 Assembly”, Intel® Corporation, available at https://software.intel.com/sites/default/files/m/d/4/1/d/8/Introduction_to_x64_Assembly.pdf, February 27, 2014.
[31]Ray Seyfarth, “Introduction to 64 Bit Windows Assembly Programming”, eBook, CreateSpace Independent Publishing Platform, October 6, 2014.
[32]Chris Lomont, “Introduction to Intel® Advanced Vector Extensions”, Intel White Paper, 23 May, 2011.
[33]Guide, P., “Intel® 64 and IA-32 Architectures Software Developer’s Manual”, Intel® Corporation, available at http://download.intel.com/design/processor/manuals/253665.pdf, Vol.1, May 2011.
[34]Auger, Anne, Benjamin Doerr, “Theory of randomized search heuristics: Foundations and recent developments”, Vol. 1. World Scientific, 2011.
[35]Ong, Yew-Soon, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong, “Classification of adaptive memetic algorithms: a comparative study”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 36, no. 1: 141-152, 2006.
[36]R. Lindner, M. Ruckert, “TU Darmstadt lattice challenge”, available at www.latticechallenge.org.
[37]G. Hanrot, X. Pujol, D. Stehle, “Analyzing blockwise lattice algorithms using dynamical systems”, In Proc. CRYPTO ’11, LNCS. Springer, 2011.
[38]“Implementing Bubble Sort with SSE”, available at http://www.codeproject.com/Articles/23558/Implementing-Bubble-Sort-with-SSE.
[39]NIST post-quantum candidates, available at https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.