2026-07-23T05:28:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6208 2024-03-06T10:37:47Z ddc:004 open_access

Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices Bai, Shi Stehlé, Damien Wen, Weiqiang Lattices Bounded Distance Decoding Problem Unique Shortest Vector Problem Sparsification We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/( sqrt(2) * 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shi Bai and Damien Stehlé and Weiqiang Wen 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.76 urn:nbn:de:0030-drops-62085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.76 eng https://creativecommons.org/licenses/by/3.0/legalcode