Study and Comparison of Lattice Sieving Algorithms
摘要
The Shortest Vector Problem, denoted as SVP, is one of the most important problems related to the security in the post-quantum cryptography, and it is defined over lattices. In this work, we present an state-of-the-art analysis of the different algorithms to solve this problem evaluating their efficiency in High Performance Computing (HPC) systems. To do this, we have modified the Shortest Vector Problem oracle used in the implementation of the Block Korkine-Zolotarev algorithm, known as BKZ, included in the General Sieve Kernel (gsk) software library to test a suite of different algorithms. The main purpose of this research is to check whether current hardness estimations apply to highly parallelized implementations. In this sense, we have tested the different algorithms in a High Performance Computing cluster and compared their performance on highly parallelized environments.