New directions in nearest neighbor searching with applications to lattice sieving

Add to your list(s) Download to your calendar using vCal

• Dr Leo Ducas, Centrum Wiskunde & Informatica (CWI), Amsterdam, the Netherlands
• Friday 29 April 2016, 14:00-15:00
• Mahanakorn Meeting Room (EE 909a).

If you have a question about this talk, please contact Cong Ling.

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) _²{0.415 n o(n)} and space (4/3)^{). 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 ^{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.

Bio: Dr Leo Ducas obtained 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.

This talk is part of the COMMSP Seminar series.

This talk is included in these lists:

• COMMSP & CP list
• COMMSP Seminar
• Mahanakorn Meeting Room (EE 909a)
• SAP Talks

Note that ex-directory lists are not shown.