Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP.

Emmanouil Doulgerakis; Thijs Laarhoven; Benne de Weger

doi:10.1007/978-3-030-51938-4_15

Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP.

Emmanouil Doulgerakis
, Thijs Laarhoven
, Benne de Weger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

Abstract

Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension d with a cost proportional to running a sieve in dimension $$d - \varTheta (d / \log d)$$, resulting in a $$2^{\varTheta (d / \log d)}$$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $$[\log (13/9) + o(1)] \cdot d / \log d$$ dimensions for free for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $$\varTheta (d / \log d)$$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.

Original language	English
Title of host publication	Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings
Editors	Abderrahmane Nitaj, Amr Youssef
Publisher	Springer
Pages	301-320
Number of pages	20
ISBN (Print)	9783030519377
DOIs	https://doi.org/10.1007/978-3-030-51938-4_15
Publication status	Published - 2020
Event	12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 - Cairo, Egypt Duration: 20 Jul 2020 → 22 Jul 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12174 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020
Country/Territory	Egypt
City	Cairo
Period	20/07/20 → 22/07/20

Funding

The authors thank Léo Ducas for helpful suggestions regarding the possible combination with his “dimensions for free”. Emmanouil Doulgerakis is supported by the NWO under grant 628.001.028 (FASOR). Thijs Laarhoven is supported by a Veni grant from NWO under project number 016.Veni.192.005.

Keywords

Closest vector problem (CVP)
Lattice enumeration
Lattice sieving
Randomized slicer
Shortest vector problem (SVP)

Access to Document

10.1007/978-3-030-51938-4_15

Cite this

Doulgerakis, E., Laarhoven, T., & de Weger, B. (2020). Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP. In A. Nitaj, & A. Youssef (Eds.), Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings (pp. 301-320). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12174 LNCS). Springer. https://doi.org/10.1007/978-3-030-51938-4_15

Doulgerakis, Emmanouil ; Laarhoven, Thijs ; de Weger, Benne. / Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP. Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings. editor / Abderrahmane Nitaj ; Amr Youssef. Springer, 2020. pp. 301-320 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{33326fb8c4fb4bf3b659b22aa06ee5e9,

title = "Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP.",

abstract = "Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension d with a cost proportional to running a sieve in dimension \$\$d - \textbackslash{}varTheta (d / \textbackslash{}log d)\$\$, resulting in a \$\$2\textasciicircum{}\{\textbackslash{}varTheta (d / \textbackslash{}log d)\}\$\$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of \$\$[\textbackslash{}log (13/9) + o(1)] \textbackslash{}cdot d / \textbackslash{}log d\$\$ dimensions for free for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the \$\$\textbackslash{}varTheta (d / \textbackslash{}log d)\$\$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.",

keywords = "Closest vector problem (CVP), Lattice enumeration, Lattice sieving, Randomized slicer, Shortest vector problem (SVP)",

author = "Emmanouil Doulgerakis and Thijs Laarhoven and \{de Weger\}, Benne",

year = "2020",

doi = "10.1007/978-3-030-51938-4\_15",

language = "English",

isbn = "9783030519377",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "301--320",

editor = "Abderrahmane Nitaj and Amr Youssef",

booktitle = "Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings",

address = "Germany",

note = "12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 ; Conference date: 20-07-2020 Through 22-07-2020",

}

Doulgerakis, E, Laarhoven, T & de Weger, B 2020, Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP. in A Nitaj & A Youssef (eds), Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12174 LNCS, Springer, pp. 301-320, 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020, Cairo, Egypt, 20/07/20. https://doi.org/10.1007/978-3-030-51938-4_15

Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP. / Doulgerakis, Emmanouil; Laarhoven, Thijs; de Weger, Benne.
Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings. ed. / Abderrahmane Nitaj; Amr Youssef. Springer, 2020. p. 301-320 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12174 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP.

AU - Doulgerakis, Emmanouil

AU - Laarhoven, Thijs

AU - de Weger, Benne

PY - 2020

Y1 - 2020

N2 - Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension d with a cost proportional to running a sieve in dimension $$d - \varTheta (d / \log d)$$, resulting in a $$2^{\varTheta (d / \log d)}$$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $$[\log (13/9) + o(1)] \cdot d / \log d$$ dimensions for free for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $$\varTheta (d / \log d)$$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.

AB - Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension d with a cost proportional to running a sieve in dimension $$d - \varTheta (d / \log d)$$, resulting in a $$2^{\varTheta (d / \log d)}$$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $$[\log (13/9) + o(1)] \cdot d / \log d$$ dimensions for free for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $$\varTheta (d / \log d)$$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.

KW - Closest vector problem (CVP)

KW - Lattice enumeration

KW - Lattice sieving

KW - Randomized slicer

KW - Shortest vector problem (SVP)

UR - https://www.scopus.com/pages/publications/85088537281

U2 - 10.1007/978-3-030-51938-4_15

DO - 10.1007/978-3-030-51938-4_15

M3 - Conference contribution

AN - SCOPUS:85088537281

SN - 9783030519377

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 301

EP - 320

BT - Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings

A2 - Nitaj, Abderrahmane

A2 - Youssef, Amr

PB - Springer

T2 - 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020

Y2 - 20 July 2020 through 22 July 2020

ER -

Doulgerakis E, Laarhoven T, de Weger B. Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP. In Nitaj A, Youssef A, editors, Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings. Springer. 2020. p. 301-320. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-51938-4_15

Sieve, Enumerate, Slice, and Lift: - Hybrid Lattice Algorithms for SVP via CVPP.

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this