Paper 2024/080
Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions
Abstract
The security of lattice-based crytography (LWE, NTRU, and FHE) depends on the hardness of the shortest-vector problem (SVP). Sieving algorithms give the lowest asymptotic runtime to solve SVP, but depend on exponential memory. Memory access costs much more in reality than in the RAM model, so we consider a computational model where processors, memory, and meters of wire are in constant proportions to each other. While this adds substantial costs to route data during lattice sieving, we modify existing algorithms to amortize these costs and find that, asymptotically, a classical computer can achieve the previous RAM model cost of
Note: Revised concrete estimates thanks to improved optimization scripts.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- latticesievingpost-quantumSVP
- Contact author(s)
- sejaques @ uwaterloo ca
- History
- 2024-04-25: revised
- 2024-01-17: received
- See all versions
- Short URL
- https://ia.cr/2024/080
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/080, author = {Samuel Jaques}, title = {Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/080}, year = {2024}, url = {https://eprint.iacr.org/2024/080} }