Paper 2015/522

Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search

Anja Becker, Nicolas Gama, and Antoine Joux

Abstract

We give a simple heuristic sieving algorithm for the $m$-dimensional exact shortest vector problem (SVP) which runs in time $2^{0.3112m +o(m)}$. Unlike previous time-memory trade-offs, we do not increase the memory, which stays at its bare minimum $2^{0.2075m +o(m)}$. To achieve this complexity, we borrow a recent tool from coding theory, known as nearest neighbor search for binary code words. We simplify its analysis, and show that it can be adapted to solve this variant of the fixed-radius nearest neighbor search problem: Given a list of exponentially many unit vectors of $\mR^m$, and an angle $\gamma\pi$, find all pairs of vectors whose angle $\leq\gamma\pi$. The complexity is sub-quadratic which leads to the improvement for lattice sieves.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Nearest neighbor searchlatticesieve
Contact author(s)
anja becker @ epfl ch
History
2015-08-24: revised
2015-05-31: received
See all versions
Short URL
https://ia.cr/2015/522
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/522,
      author = {Anja Becker and Nicolas Gama and Antoine Joux},
      title = {Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search},
      howpublished = {Cryptology ePrint Archive, Paper 2015/522},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/522}},
      url = {https://eprint.iacr.org/2015/522}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.