Paper 2022/195
Quantum and Classical Algorithms for Bounded Distance Decoding
Richard Allen, Ratip Emin Berker, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- LatticesBDDLLLCryptanalysisQuantum Cryptography
- Contact author(s)
- richrossallen @ gmail com
- History
- 2022-02-20: received
- Short URL
- https://ia.cr/2022/195
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/195,
author = {Richard Allen and Ratip Emin Berker and Sílvia Casacuberta and Michael Gul},
title = {Quantum and Classical Algorithms for Bounded Distance Decoding},
howpublished = {Cryptology ePrint Archive, Paper 2022/195},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/195}},
url = {https://eprint.iacr.org/2022/195}
}
