Welcome to the resource topic for 2015/522
Title:
Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search
Authors: Anja Becker, Nicolas Gama, 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.
ePrint: https://eprint.iacr.org/2015/522
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .