Improving Convergence and Practicality of Slide-type Reductions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2023

Improving Convergence and Practicality of Slide-type Reductions

Résumé

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle.
Fichier principal
Vignette du fichier
Convergence_of_Slide_Reduction.pdf (612.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03983826 , version 1 (11-02-2023)

Identifiants

Citer

Jianwei Li, Michael Walter. Improving Convergence and Practicality of Slide-type Reductions. Information and Computation, In press, ⟨10.1016/j.ic.2023.105012⟩. ⟨hal-03983826⟩
24 Consultations
46 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More