.png){kind=icon}
.png){kind=icon}
Return
A Study on Parallel Tuple Sieve Algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0172-4_6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
As the development of large-scale quantum computing continues to progress, it is widely recognized that the security of current cryptographic systems, such as RSA and elliptic curve cryptography, is seriously threatened. These systems depend on the hardness of integer factorization problems or discrete logarithms problems on elliptic curves, both of which are vulnerable to quantum attacks. In response, lattice-based cryptography has emerged as a promising next-generation solution based on the hardness of the Shortest Vector Problem (SVP) and its approximate variants on lattices. However, the deployment of lattice-based cryptography necessitates careful parameter optimization and insights from research into attack algorithms and large-scale computational challenges. Sieve algorithm is one of the most practical lattice attack algorithms. In this work, we propose a parallelized version of the Tuple Sieve algorithm, an approximate SVP-solving algorithm that offers reduced memory usage compared to the Parallel Gauss Sieve algorithm introduced by Ishiguro et al. at PKC 2014. Our algorithm was implemented and tested on a multi-core CPU. Evaluations on low-dimensional lattices, such as a 42-dimensional lattice using 16 cores, demonstrated a speedup of approximately 31x over the conventional Tuple Sieve algorithm, alongside a 43% reduction in memory usage compared to the original Tuple Sieve; and a 67% reduction in spacial cost derives compared to the Parallel Gauss Sieve.
Keywords:
Post-Quantum Cryptography
Lattice
Parallel Tuple Sieve Algorithm
Journal
M
IF:
0
Papers:
26
Citations:
0