A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem

IEEE Access

Zedong Sun¹  Yonghui Zheng¹  Chunxiang Gu¹ 

[1] State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, China;

关键词: Lattice theory;    post-quantum cryptography;    lattice-based cryptography;    shortest vector problem;    sieve algorithm;   

DOI  :  10.1109/ACCESS.2020.3031276

来源: DOAJ

【 摘 要 】

As a category of algorithms to solve the shortest lattice vector problem, sieve algorithms have drawn more and more attention due to the prominent performance in recent years. Enumeration algorithms used to perform better in practice even though sieve algorithms are asymptotically faster. Combined with techniques like locality-sensitive hashing and rank reduction, sieve algorithms now are capable of competing with enumeration algorithms. In this work, we study sieve algorithms in solving the shortest vector problem on lattices by categorizing various sieve algorithms and elaborating on ideas and techniques used to improve sieve algorithms. In addition, we present several prospective directions worth future research.

【 授权许可】

Unknown