Cryptology ePrint Archive: Report 2022/195
Quantum and Classical Algorithms for Bounded Distance Decoding
Richard Allen and Ratip Emin Berker and Sílvia Casacuberta and Michael Gul
Abstract: In this paper, we provide a comprehensive overview of a recent debate over the quantum versus classical solvability of bounded distance decoding (BDD). Specifically, we review the work of Eldar and Hallgren [EH22], [Hal21] demonstrating a quantum algorithm solving $\lambda_1 2^{-\Omega(\sqrt{k \log q})}$-BDD in polynomial time for lattices of periodicity $q$, finite group rank $k$, and shortest lattice vector length $\lambda_1$. Subsequently, we prove the results of [DvW21a], [DvW21b] with far greater detail and elaboration than in the original work. Namely, we show that there exists a deterministic, classical algorithm achieving the same result.
Category / Keywords: public-key cryptography / Lattices, BDD, LLL, Cryptanalysis, Quantum Cryptography
Date: received 18 Feb 2022
Contact author: richrossallen at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20220220:204001 (All versions of this report)
Short URL: ia.cr/2022/195
[ Cryptology ePrint archive ]