Sieve, enumerate, slice, and lift:: Hybrid lattice algorithms for svp via cvpp

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
TitelProgress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Proceedings
RedacteurenAbderrahmane Nitaj, Amr Youssef
UitgeverijSpringer Gabler
Pagina's301-320
Aantal pagina's20
ISBN van geprinte versie9783030519377
DOI's
StatusGepubliceerd - 2020
Evenement12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020 - Cairo, Egypte
Duur: 20 jul 202022 jul 2020

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12174 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020
LandEgypte
StadCairo
Periode20/07/2022/07/20

Vingerafdruk Duik in de onderzoeksthema's van 'Sieve, enumerate, slice, and lift:: Hybrid lattice algorithms for svp via cvpp'. Samen vormen ze een unieke vingerafdruk.

Citeer dit