Imperial College London > Talks@ee.imperial > COMMSP Seminar > New directions in nearest neighbor searching with applications to lattice sieving

## Log inImperial users Other users No account?## Information onFinding a talk Adding a talk Syndicating talks Who we are Everything else |
## New directions in nearest neighbor searching with applications to lattice sievingAdd 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) 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 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 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:Note that ex-directory lists are not shown. |
## Other listsWind Farms Powertalk Type the title of a new list here## Other talksStability and power sharing in microgrids Intelligent Systems and Networks Seminar iCore Seminar: From Distributed Optimization to In-Network Data Processing in Wireless Ad-Hoc and Sensor Networks Latest developments of CMOS time-resolved imagers and their applications in life sciences Cluttered Scene Segmentation Using the Symmetry Constraint |