Research On The Approximate Shortest Lattice Vector Problem

With the continuous development of quantum computing technology,polynomial-time quantum algorithms are proposed to solve hard algebraic hard problems such as integer factorization and discrete logarithm problem.Therefore,many public-key cryptosystems such as RSA,ECC and DSA,whose security depend on the hardness of these hard problems,are exposed to severe vulnerability.Information transmission security and network communication security are facing potential threats.Facing the challenge of quantum computing,making post-quantum cryptographic standard becomes a important task.Quantum-resistant hard computing problems are intensively investigated both in cryptographic and computing algebra.Computing problems of lattice caused great concern because of its quantum resistance property,and lattice-based public-key cryptosystems also has great properties such as strong security reduction in theory and high efficiency in practice.As a essential mathematic problem in lattice theory,the approximate Shortest Vector Problem(SVP)is significant for the security assessment of lattice-based cryptosystems.In theory,the security proof of many lattice-based cryptosystems are reduced to the hardness of the approximate SVP;In practice,the efficiency of searching short lattice vectors is a practical measurement of lattice-based cryptosystem security.Based on the existing algorithms for solving approximate SVP,this thesis aims to fix the theoretical model,improve the algorithm efficiency and explore new type SVP algorithm,and accomplish three works:1.Proposed a new vector sampling strategy,and make improvement on random sampling reduction algorithm for solving approximate SVP.Focusing on the defect in vector sampling strategy,by using “natural number representation” of lattice vector,this thesis prove that the vectors sampled in a modified structure of candidate set have length following normal distribution asymptotically and verify it in low and middle dimensional lattice.Then this thesis proposed an enumeration-like random sampling algorithm to sample very short lattice vector and embed it into the framework of random sampling reduction algorithm.Comparing with other trivial sampling strategies,the new sampling strategy accelerates the random sampling reduction algorithm.And this thesis also compare the efficiency of different lattice reduction algorithms on solving approximate SVP.This work shows the feasibility of our new sampling strategy,and reveal the effectiveness of stronger reduction algorithm.2.Make improvement on discrete pruning enumeration algorithm.Enumeration algorithms with low success probability need to repeatedly run on different basis.Focusing on this property and inspired by the first work,this thesis proposed three methods to optimize discrete pruning algorithm.First,take full usage of the middle result when recover lattice vector form natural number vector,and store some lattice vector to reduce the basis.Second,define G-S squared length of basis to quantitatively describe lattice basis property,and control the G-S squared length of basis during enumeration procedure.Third,use a simplified version of BKZ algorithm,one-tour BKZ,to take balance between enumeration and lattice reduction.This algorithm shows higher efficiency in practice,comparing with traditional enumeration with various pruning strategies.In particular,this algorithm has better experimental result than extreme pruning,which is the state-of-art pruning strategy implemented in BKZ2.0 for analyzing lattice-based cryptographic security.3.Apply genetic algorithm to solving approximate SVP.This thesis proposed a genetic SVP algorithm by using natural number representation as chromosome encode.In the design of evolution mechanism,we use the ranking-based selection with elitist strategy to avoid frequent floating point computation,and to avoid local stagnation,we propose a restart strategy utilizing good individuals to reduce lattice basis and improve the property of lattice basis,which is enlightened by random sampling reduction algorithms.The genetic algorithm with restart outperforms the trivial genetic algorithm in solving approximate SVP,and also outperforms classic enumeration algorithms on lattices under 100 dimension in practice.Besides,its implementation efficiency is close to the state-of-art extreme pruning enumeration.These works enrich the theoretical tools for analyzing SVP algorithms,optimize the current SVP algorithms and explore the application feasibility of intelligent algorithms in solving approximate SVP.This thesis provides improved algorithm and important experimental data for solving approximate SVP,and is of great significance to the security parameter evaluation of lattice-based cryptosystem.