Lattice-related Algorithms Research

In the age of data explosion,information security issues have become increasingly prominent,so cryptography plays a more and more important role in the information era.Lattice-based cryptography has been attracted extensive attention because of its incomparable advantages of low energy consumption and resist quantum attacks.The lattice-related reduction algorithms are playing an important role in lattice-based cryptography.Lattice-related reduction algorithms are mainly to solve the two problems of SVP and CVP,the classic lattice reduction algorithms mainly include LLL,BKZ,GaussSieve,NV,etc.The lattice-related reduction algorithms have a wide range of applications in computer algebra,integer programming,and cryptography.This paper mainly focuses on solving the SVP problem by optimizing the time complexity of random selection algorithm,using the strategy of replacing the global radius with the local radius to optimize the sphere decoding algorithm for solving the CVP problem.The details are as follows:Firstly,the optimal space complexity of the random selection algorithm to solve the SVP problem is 20.2075n+o(n)at present.The high space complexity of the random selection algorithm has become a stumbling block to its competition with the enumeration algorithm under the condition of the dimension of lattice is high.The Filtered triple sieving algorithm breaked the bottleneck of the random selection algorithm and reduce the space complexity of the random selection algorithm to 20.1887n+o(n).However,the time complexity of this algorithm is as high as 20 4812n+o(n).In order to optimize the time complexity of the Filtered triple sieving algorithm,we propose a new random selection algorithm,FT-HashSieve,can solve SVP problem with time complexity 20.4098n+o(n)and keep the space complexity 20.1887n+o(n).At the same time,we use the transformation of FT-HashSieve algorithm to solve the CVP problem which is the least space complexity algorithm to solve the CVP problem at present.Secondly,the sphere decoding algorithm SDA is one of the effective methods to solve the CVP problem,effective pruning technology is one of the effective ways to reduce the time complexity of SDA.The radius R in the sphere decoding algorithm determines the size of the search space.We propose a strategy to replace the global search radius with the dynamic radius firstly.The core idea of our algorithm is to sacrifice relatively small solution accuracy to exchange for greater time complexity reduction.