Welcome to the resource topic for 2016/713
Title:
Tuple lattice sieving
Authors: Shi Bai, Thijs Laarhoven, Damien Stehle
Abstract:Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as 2^{0.2075 n + 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 2^{0.1887 n + o(n)}. The naive algorithm for this triple sieve runs in time 2^{0.5661 n + o(n)}. With appropriate filtering of pairs, we reduce the time complexity to 2^{0.4812 n + 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 tradeoff between the memory-intensive sieving and the asymptotically slower enumeration.
ePrint: https://eprint.iacr.org/2016/713
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .