Improved Reduction from the Bounded
Distance Decoding Problem to the Unique
Shortest Vector Problem in Lattices
Shi Bai, Damien Stehlé and Weiqiang Wen
Abstract: We present a probabilistic polynomial-time reduction from
the lattice Bounded Distance Decoding (BDD) problem with parameter 1/(sqrt(2) * gamma)
to the unique Shortest Vector Problem (uSVP) with parameter gamma
for any gamma > 1 that is polynomial in the lattice dimension n. 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 sparsication [Khot, FOCS, 2003] before
resorting to Kannan's embedding, in order to boost the uSVP parameter.
Download: pdf.
Homepage