Tuple lattice sieving

Shi Bai, Thijs Laarhoven, Damien Stehlé

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

17 Citaten (Scopus)


Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving the SVP require space which (heuristically) grows as 20.2075n+o(n), where n is the lattice dimension. In high dimensions,
the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity.
We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as 20.1887n+o(n). The naive algorithm for this triple
sieve runs in time 20.5661n+o(n). With appropriate filtering of pairs, we reduce the time complexity to 20.4812n+o(n) while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous trade-off between the memory-intensive sieving and the asymptotically slower enumeration.
Originele taal-2Engels
Pagina's (van-tot)146-162
TijdschriftLMS Journal of Computation and Mathematics
Nummer van het tijdschriftA
StatusGepubliceerd - 1 jan 2016

Vingerafdruk Duik in de onderzoeksthema's van 'Tuple lattice sieving'. Samen vormen ze een unieke vingerafdruk.

Citeer dit