A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem
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 w...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9224855/ |
| _version_ | 1811210656125288448 |
|---|---|
| author | Zedong Sun Chunxiang Gu Yonghui Zheng |
| author_facet | Zedong Sun Chunxiang Gu Yonghui Zheng |
| author_sort | Zedong Sun |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T04:58:30Z |
| format | Article |
| id | doaj.art-b45af6d1e50543ca821da0f429325edc |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T04:58:30Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-b45af6d1e50543ca821da0f429325edc2022-12-22T03:47:03ZengIEEEIEEE Access2169-35362020-01-01819047519048610.1109/ACCESS.2020.30312769224855A Review of Sieve Algorithms in Solving the Shortest Lattice Vector ProblemZedong Sun0https://orcid.org/0000-0003-1762-6301Chunxiang Gu1https://orcid.org/0000-0003-3860-1939Yonghui Zheng2State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, ChinaState Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, ChinaAs 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.https://ieeexplore.ieee.org/document/9224855/Lattice theorypost-quantum cryptographylattice-based cryptographyshortest vector problemsieve algorithm |
| spellingShingle | Zedong Sun Chunxiang Gu Yonghui Zheng A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem IEEE Access Lattice theory post-quantum cryptography lattice-based cryptography shortest vector problem sieve algorithm |
| title | A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem |
| title_full | A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem |
| title_fullStr | A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem |
| title_full_unstemmed | A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem |
| title_short | A Review of Sieve Algorithms in Solving the Shortest Lattice Vector Problem |
| title_sort | review of sieve algorithms in solving the shortest lattice vector problem |
| topic | Lattice theory post-quantum cryptography lattice-based cryptography shortest vector problem sieve algorithm |
| url | https://ieeexplore.ieee.org/document/9224855/ |
| work_keys_str_mv | AT zedongsun areviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem AT chunxianggu areviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem AT yonghuizheng areviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem AT zedongsun reviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem AT chunxianggu reviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem AT yonghuizheng reviewofsievealgorithmsinsolvingtheshortestlatticevectorproblem |