Paper 2024/1358

Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD

Lynn Engelberts, Centrum Wiskunde & Informatica, QuSoft
Simona Etinski, Centrum Wiskunde & Informatica
Johanna Loyer, Centrum Wiskunde & Informatica
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.