International Association
for Cryptologic Research

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.