格上困难问题求解的智能筛选算法及测试

Intelligent sieve algorithms and tests for solving the hard problems on lattice

在总结格密码困难问题发展和求解中关键理论与技术的基础上,从渐进最短向量问题(approx-SVP)入手,对比分析了经典格基约减算法的优缺点,重点研究了其求解推进过程中的关键技术和算法性能瓶颈,归纳了进行格基约减进而求解渐进最短向量问题的一般步骤。在经典的格向量假设基础上,提出了格向量智能筛选模型。通过优化向量选择的路径等方法,设计了基于最优路径分布的智能筛选算法、逆向求解智能验证算法和近似最短向量智能筛选算法三种求解最短向量问题(SVP)的算法,测试结果表明算法在求解格上困难问题上有效。

The key theories and technologies of the hard problems on lattice were combed,and then from the approx-shortest vector problems(approx-SVP),the advantages and disadvantages of the classic reduction algorithms were in-depth comparative analyzed.The key techniques and algorithms in the process of solving propulsion performance bottlenecks were thoroughly studied,and the general steps of basis reduction and approx-SVP were summarized.An intelligent reducing model of approaching the shortest vector was proposed based on the classic hypothesis on lattice. Three variants of hypothesis for solving lattice reduction and the shortest vector problems(SVP) were proposed:intelligent sieving algorithm based on optimal path distribution,intelligent verifying algorithm for reversal solution solving,and intelligent sieving algorithm for the approximately shortest vector. The performance tests show the effectiveness of algorithms.