Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices (original) (raw)

Paper 2016/753

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

Shi Bai, 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\gammagamma for any gamma>1\gamma>1gamma>1 that is polynomial in the lattice dimension nnn. 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.

BibTeX

@misc{cryptoeprint:2016/753, author = {Shi Bai and Damien Stehle and Weiqiang Wen}, title = {Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/753}, year = {2016}, url = {https://eprint.iacr.org/2016/753} }