Quantum and Classical Algorithms for Bounded Distance Decoding

Richard Allen; Ratip Emin Berker; Sílvia Casacuberta; Michael Gul

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 $λ_{1} 2^{- Ω (\sqrt{k \log q})}$ -BDD in polynomial time for lattices of periodicity $q$ , finite group rank $k$ , and shortest lattice vector length $λ_{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: Lattices BDD LLL Cryptanalysis Quantum 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},
      url = {https://eprint.iacr.org/2022/195}
}