iCore seminar by Dr Leo Ducas (CWI, Amsterdam, the Netherlands)
29 April 2016 (Friday) - from 14:00 to 15:00
Room 909a, level 9, EEE Dept. @ Imperial College
Dr Leo Ducas obtained his PhD in cryptography at Ecole Normale Superieure, with a dissertation
on theoretical and practical aspect of digital signatures based on lattice problems. After a year of post-doc
at University of California San Diego, he has moved to CWI, Amsterdam, focusing on cryptographic design from
lattices and cryptanalysis.
Seminar Title: "New directions in nearest neighbor searching with applications to lattice sieving"
Abstract: A fundamental problem in Complexity Theory and Cryptography is to find short vectors in
a lattice (SVP). Lattice sieving algorithm are asymptotically the best algorithms for this task, the simplest of which
runs heuristically in time (4/3)^{n+o(n)} ~ 2^{0.415 n + o(n)} and space (4/3)^(n/2 + o(n)). Recently, it has been
showed that such algorithm could be sped up using Nearest-Neighbor Search tools: with some pre-processing and
more memory, it is possible to find the closest point from a list L to a target t in time sub-linear in the
length of L.
The Spherical locality-sensitive hash (LSH) family previously studied by Andoni et al. was thought to be optimal
for that task. As we will show, it can in fact be improved in the *dense regime*, i.e. when the length of the
list L is at least exponential in the dimension n, as in our sieving application. We proceed in two steps.
First we show new complexity bounds provided assuming that we are given an efficient list-decoding oracle for random
spherical codes, where by efficient we mean that it has a polynomial overhead for exponentially large outputs.
Secondly, to instantiate the decoding oracle, we replace the random code by a direct product of polylog(n) random
codes. We show that the additional structure in these concatenation codes allows us to decode efficiently using
techniques similar to lattice enumeration, while at the same time not significantly affecting the first claim.
We finally apply those results to sieving algorithms for solving the shortest vector problem (SVP) on lattices,
and show that this leads to a heuristic time complexity for solving SVP in dimension n of
(3/2)^{n/2 + o(n)} ~ 2^{0.292 n + o(n)}. This asymptotically improves upon the previous best algorithms for solving
SVP which use spherical LSH and run in time 2^{0.298 n + o(n)}. Experiments with the GaussSieve validate the claimed
speedup and suggests that the hidden 2^{o(n)} factor is also significantly better. Our implementation is available
under an open-source license.