Cryptology ePrint Archive: Report 2016/753

Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices

Shi Bai and Damien Stehle and Weiqiang Wen

Abstract: We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/($\sqrt{2}\cdot\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 sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.

Category / Keywords: Lattices, Bounded Distance Decoding Problem, Unique Shortest Vector Problem, Sparsification

Original Publication (with minor differences): ICALP 2016

Date: received 4 Aug 2016, last revised 31 Aug 2016

Contact author: weiqiang wen at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Version: 20160831:155711 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]