Paper 2024/080

Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions

Samuel Jaques, University of Waterloo
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 $2^{0.2925d+o(d)}$ to sieve a $d$-dimensional lattice for a computer existing in 3 or more spatial dimensions, and can reach $2^{0.3113d+o(d)}$ in 2 spatial dimensions, where "spatial dimensions" are the dimensions of the physical geometry in which the computer exists. Under some assumptions about the constant terms of memory access, we estimate increases in bit security between $7$ to $23$ bits for different Kyber parameter sets and $8$ to $22$ bits for Dilithium.

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.