Paper 2024/1358
Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD
Abstract
Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the classical [BDGL16] and quantum [BCSS23] setting. Recently, sieving has also become an important tool in code-based cryptanalysis. Specifically, using a sieving subroutine, [GJN23, DEEK24] presented a variant of the information-set decoding (ISD) framework, which is commonly used for attacking cryptographically relevant instances of the decoding problem. The resulting sieving-based ISD framework yields complexities close to the best-performing classical algorithms for the decoding problem such as [BJMM12, BM18]. It is therefore natural to ask how well quantum versions perform. In this work, we introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. In particular, using quantum-walk techniques, we provide a speed-up over the best known classical algorithm from [DEEK24] and over a variant using Grover's algorithm [Gro96]. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering, inspired by the quantum-walk algorithm for lattice sieving from [CL21]. We complement our asymptotic analysis of the quantum algorithms with numerical results, and observe that our quantum speed-ups for code sieving behave similarly as those observed in lattice sieving. In addition, we show that a natural quantum analog of the sieving-based ISD framework does not provide any speed-up over the first presented quantum ISD algorithm [Ber10]. Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms [KT17, Kir18].
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Quantum cryptanalysisQuantum walksNear-neighbor searchCode sievingDecoding problemInformation-set decoding
- Contact author(s)
-
lynn engelberts @ cwi nl
simona etinski @ cwi nl
johanna loyer @ cwi nl - History
- 2024-08-30: approved
- 2024-08-29: received
- See all versions
- Short URL
- https://ia.cr/2024/1358
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1358, author = {Lynn Engelberts and Simona Etinski and Johanna Loyer}, title = {Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for {ISD}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1358}, year = {2024}, url = {https://eprint.iacr.org/2024/1358} }