Improved analysis of the reduction from BDD to uSVP

In ICALP 2016, Bai, Stehle and Wen showed that for polynomially bounded parameter gamma, the Bounded Distance Decoding (BDD) problem with parameter 1/(root 2 gamma) can be probabilistically reduced to the unique Shortest Vector Problem (uSVP) with parameter gamma. Their reduction is based on the lattice sparsification and embedding techniques. In this paper, we improve their analysis for specific values of the parameter and prove that BDD1/(root 2 gamma) can be reduced to uSVP(gamma 1) with a slightly larger gap. The improvement follows from a careful study of the radius of a sphere which contains at most polynomial number of vectors, then a proper choice of the parameter in the embedding lattice is used to obtain a unique lattice with a larger gap. Our result shows that the equivalence between BDD1/(root 2 gamma) and uSVP gamma does not hold under the assumption that uSVP gamma does not reduce to uSVPy, for any two constants gamma < gamma'. (C) 2019 Elsevier B.V. All rights reserved.