Sieving for shortest vectors in lattices using angular locality-sensitive hashing

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

48 Citaten (Scopus)

Samenvatting

By replacing the brute-force list search in sieving algorithms with Charikar’s angular locality-sensitive hashing (LSH) method, we get both theoretical and practical speedups for solving the shortest vector problem (SVP) on lattices. Combining angular LSH with a variant of Nguyen and Vidick’s heuristic sieve algorithm, we obtain heuristic time and space complexities for solving SVP of 2^0.3366n+o(n) and 2^0.2075n+o(n) respectively, while combining the same hash family with Micciancio and Voulgaris’ GaussSieve algorithm leads to an algorithm with (conjectured) heuristic time and space complexities of 2^0.3366n+o(n). Experiments with the GaussSieve-variant show that in moderate dimensions the proposed HashSieve algorithm already outperforms the GaussSieve, and the practical increase in the space complexity is much smaller than the asymptotic bounds suggest, and can be further reduced with probing. Extrapolating to higher dimensions, we estimate that a fully optimized and parallelized implementation of the GaussSieve-based HashSieve algorithm might need a few core years to solve SVP in dimension 130 or even 140. Keywords: Lattices; Shortest vector problem (SVP); Sieving algorithms; Approximate nearest neighbor problem; Locality-sensitive hashing (LSH)
Originele taal-2Engels
TitelAdvances in Cryptology - CRYPTO 2015 (35th Annual Cryptology Conference, Santa Barbara CA, USA, August 16-20, 2015), Part I
RedacteurenR. Gennaro, M. Robshaw
Plaats van productieBerlin
UitgeverijSpringer
Pagina's3-22
ISBN van geprinte versie978-3-662-47988-9
DOI's
StatusGepubliceerd - 2015
Evenement35th Annual International Cryptology Conference (CRYPTO 2015), August 16-20, 2015, Santa Barbara, CA, USA - University of California, Santa Barbara (UCSB) , Santa Barbara, CA, Verenigde Staten van Amerika
Duur: 16 aug 201520 aug 2015
https://www.iacr.org/conferences/crypto2015/

Publicatie series

NaamLecture Notes in Computer Science
Volume9215
ISSN van geprinte versie0302-9743

Congres

Congres35th Annual International Cryptology Conference (CRYPTO 2015), August 16-20, 2015, Santa Barbara, CA, USA
Verkorte titelCRYPTO 2015
LandVerenigde Staten van Amerika
StadSanta Barbara, CA
Periode16/08/1520/08/15
Ander35th Annual Cryptology Conference on Advances in Cryptology
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Sieving for shortest vectors in lattices using angular locality-sensitive hashing'. Samen vormen ze een unieke vingerafdruk.

Citeer dit