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

Onderzoeksoutput: Boek/rapportRapportAcademic

48 Downloads (Pure)


By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity. Keywords: lattices, shortest vector problem, sieve algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing
Originele taal-2Engels
Aantal pagina's24
StatusGepubliceerd - 2014

Publicatie series

NaamCryptology ePrint Archive

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