Welcome to the resource topic for
**2016/753**

**Title:**

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

**Authors:**
Shi Bai, Damien Stehle, 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.

**ePrint:**
https://eprint.iacr.org/2016/753

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .