The Optimization Of Heuristic Sieve Methods In Lattices

Under the rapid development of quantum computing,traditional public key cryp-tosystems are difficult to resist the attacks of quantum computers in the future.In order to ensure information security,it is urgent to study cryptosystems that can resist quan-tum attacks.Lattice-based cryptography is one of the best cryptographic schemes that can resist quantum attacks.As the core of cryptosystem,difficult problems in lattices are the focus of many scholars.The research on the algorithm for solving lattice-hard problems can not only provide guarantee for the security of lattice-based cryptography,but also attack other cryptosystems.In this thesis,Shortest Vector Problem and Closest Vector Problem are studied.Moreover,a class of efficient algorithms,heuristic sieves,are optimized to solve these problems.The first content of this thesis is to use K-Means Local Sensitive Hash(K-Means LSH)derived from machine learning to optimize NV-Sieve and GaussSieve heuristic sieve methods,and obtain three research results.Firstly,K-Means Local Sensitive Hash has better performance than Cross-polytope Local Sensitive Hash(CP LSH)through analysis and experiment;Secondly,K-Means LSH is used to optimize the two sieve methods,and experiments show that the optimization method has higher efficiency and flexibility than CP Sieve based on CP LSH optimization proposed by Thijs Laarhoven et al.Thirdly,the optimized NV-Sieve is extended to solve Closest Vector Problem.The second content of this thesis is to optimize the space consumption of GaussSieve,which is a research field that few scholars dabble in at present.Aiming at the list that consumes the most space in GaussSieve algorithm,the author optimizes it by adopting NV-Sieve's core sieve step.Judging from the experimental data,the optimization method does not change the main term of space complexity,effectively reduces its polynomial factor,and at the same time introduces polynomial-level time consumption,which can be regarded as a method to balance time and space consump-tion.