×

zbMATH — the first resource for mathematics

Tuple lattice sieving. (English) Zbl 1404.11140
Summary: 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 \(2^{0.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 \(2^{0.1887n+o(n)}\). The naive algorithm for this triple sieve runs in time \(2^{0.5661n+o(n)}\). With appropriate filtering of pairs, we reduce the time complexity to \(2^{0.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.

MSC:
11Y16 Number-theoretic algorithms; complexity
11H06 Lattices and convex bodies (number-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Aggarwal, Proceedings of the STOC pp 733– (2015)
[2] DOI: 10.1515/JMC.2008.009 · Zbl 1193.11117
[3] Semaev, Proceedings of the CALC pp 181– (2001)
[4] Ajtai, Proceedings of the STOC pp 601– (2001)
[5] DOI: 10.1145/1597036.1597050 · Zbl 1300.11133
[6] Micciancio, Proceedings of SODA (2010)
[7] DOI: 10.1007/978-3-540-88702-7_5 · Zbl 1161.81324
[8] Laarhoven, DCC 77 pp 375– (2015)
[9] Laarhoven, Proceedings of the CRYPTO pp 3– (2015)
[10] Gama, Proceedings of the EUROCRYPT pp 257– (2010)
[11] Kannan, Proceedings of the STOC pp 99– (1983)
[12] Fitzpatrick, Proceedings of the LATINCRYPT pp 288– (2015)
[13] Chen, Proceedings of the ASIACRYPT pp 1– (2011)
[14] Hoffstein, Proceedings of the ANTS pp 267– (1998)
[15] Hanrot, Proceedings of CRYPTO pp 170– (2007)
[16] Becker, Proceedings of the SODA pp 10– (2016)
[17] Hanrot, IWCC pp 159– (2011)
[18] Gentry, Proceedings of the STOC pp 197– (2008)
[19] Tammela, Sov. Math. Dokl. 14 pp 651– (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.