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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Study and Comparison of Lattice Sieving Algorithms

  • Miguel Ángel González de la Torre,
  • Luis Hernández Encinas,
  • Diego Rojas Rodríguez

摘要

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.