Y-sparse Representations Of Short Lattice Vectors And Algorithms For The Shortest Vector Problem (SVP) In Lattices

With the recent deep research into quantum computers, the hardness of prime factorization and discrete logarithm has collapsed, on which, yet, the security of most widely-used public-key cryptography nowadays is based. Therefore, it attracts more and more research interests from the cryptology community to build the ”post-quantum”crypto-systems, which is secure against quantum computers. Among the several recentlyproposed post-quantum crypto-systems, lattice-based cryptography, especially NTRU, is gradually becoming a hot-spot in top cryptology conferences and journals in recent years.The shortest vector problem, abbreviated as SVP, is one of the most important problems in the geometry of numbers,and, moreover, the security of lattice-based cryptography is based on that. In the thesis, we research deeply into the shortest vector problem(SVP), and propose the y-sparse representations of short lattice vectors under a BKZreduced basis, and, meanwhile, design some SVP algorithms through the y-sparse representations, including the genetic algorithm, the phase-based enumeration algorithm, the simulated annealing algorithm, and the random sampling algorithm for the shortest vector problem. The main contributions are threefold as follows:? First, the thesis proposes a novel type of y-sparse integer representation for the short lattice vectors under a BKZ-reduced basis, and, meanwhile, estimate the short upper bounds of the elements in the integer representations for the short lattice vectors and discover their sparsity. The y-sparse representation of the short lattice vectors is of independent interests.? Second, the thesis, for the first time, introduces computational-intelligent ideas of genetic algorithm and simulated annealing algorithm into solving the shortest vector problem, and, furthermore, through Markov analysis and experimental results show that the ideas are e ffi cient for searching the shortest lattice vectors.? Third, the thesis proposes a new conception of phase in y-sparse representation, and,through the ascending order of the nonzero elements in phases, proposes a fast phasebased enumeration algorithm for the shortest vector problem. The experimental results show that this phase-based enumeration algorithm is a fast and e ffi cient SVP solver compared to the mainstream SVP enumeration algorithms.