A new lattice reduction algorithm based on genetic strategy

被引：0
|
作者：
Liu, Xiang-Hui [1 ,2 ]
Han, Wen-Bao [1 ,2 ]
Quan, Jian-Xiao [3 ]
机构：
[1] PLA Information Engineering University
[2] State Key Laboratory of Mathematical Engineering and Advanced Computing
[3] Jiangnan Institute of Technology
来源：
Dianzi Yu Xinxi Xuebao/Journal of Electronics and Information Technology | 2013年 / 35卷 / 08期
关键词：
Cryptography; Genetic algorithm; Lattice reduction; LLL algorithm; Shortest Vector Problem (SVP) challenge;
D O I：
10.3724/SP.J.1146.2012.01560
中图分类号：
学科分类号：
摘要：
Lattice reduction algorithms play an important role in the field of cryptanalysis. In this paper, based on the strategies of genetic algorithm, a new lattice reduction algorithm is proposed through the transformation of the initial lattice basis. The new algorithm always can obtain a shorter vector and a higher quality basis compared with the original algorithms. By the new algorithm, some lattice bases of the Shortest Vector Problem (SVP) challenge are experienced and the outputs of the new algorithm can always reach or break the records on the internet which illustrates that the new algorithm behaves well.
引用
收藏
页码：1940 / 1945
页数：5
相关论文
共 12 条
  • [1] Lenstra A.K., Lenstra H.W., Lovasz L., Factoring polynomials with rational coefficients, Mathematiche Annalen, 261, 4, pp. 515-534, (1982)
  • [2] Coppersmith D., Finding a small root of a univariate modular equation, LNCS, 1070, pp. 155-165, (1996)
  • [3] Santanu S., Some results on cryptanalysis of RSA and factorization, (2011)
  • [4] Kumar R.S., Narasimam C., Setty S.P., Lattice based tools in cryptanalysis for public key cryptography, International Journal of Network Security & Its Applications, 4, 2, pp. 155-162, (2012)
  • [5] Schnorr C.P., Block reduced lattice bases and successive minima, Combinatorics, Probability and Computing, 3, 4, pp. 507-522, (1994)
  • [6] Hanrot G., Pujol X., Stehle D., Terminating BKZ
  • [7] TU Darmstadt Lattice challenge
  • [8] Backes W., Wetzel S., The effect of sorting on lattice basis reduction
  • [9] Nguyen P.Q., Valle B., The LLL Algorithm: Survey and Applications, pp. 19-71, (2009)
  • [10] Shoup V., Number Theory Library (NTL) for c++
12