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

*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.

**Category / Keywords: **public-key cryptography / Nearest neighbor search, lattice, sieve

**Date: **received 31 May 2015, last revised 24 Aug 2015

**Contact author: **anja becker at epfl ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20150824:143217 (All versions of this report)

**Short URL: **ia.cr/2015/522

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]