TY - GEN
T1 - Improved reduction from the bounded distance decoding problem to the unique shortest vector problem in lattices
AU - Bai, Shi
AU - Stehlé, Damien
AU - Wen, Weiqiang
PY - 2016/8/1
Y1 - 2016/8/1
N2 - We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/(√2 γ) to the unique Shortest Vector Problem (uSVP) with parameter γ for any γ > 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.
AB - We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/(√2 γ) to the unique Shortest Vector Problem (uSVP) with parameter γ for any γ > 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.
KW - Bounded distance decoding problem
KW - Lattices
KW - Sparsification
KW - Unique shortest vector problem
UR - https://www.scopus.com/pages/publications/85012874573
U2 - 10.4230/LIPIcs.ICALP.2016.76
DO - 10.4230/LIPIcs.ICALP.2016.76
M3 - Conference contribution
AN - SCOPUS:85012874573
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -