Séminaire ICI : Weiqiang Wen

Titre du séminaire et orateur

Improved reduction from BDD to uSVP.

Weiqiang Wen, IRISA.

Date et lieu

Lundi 9 mars 2020, 14h.

ENSEA, salle 384.


In this talk, I will present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/(√2⋅γ) to the unique Shortest Vector Problem (uSVP) with parameter γ for any γ>1. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.