Paper 2024/907

Reducing the Number of Qubits in Quantum Information Set Decoding

Clémence Chevignard, Univ Rennes, Inria, CNRS, IRISA
Pierre-Alain Fouque, Univ Rennes, Inria, CNRS, IRISA
André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA
Abstract

This paper presents an optimization of the memory cost of the quantum Information Set Decoding (ISD) algorithm proposed by Bernstein (PQCrypto 2010), obtained by combining Prange's ISD with Grover's quantum search. When the code has constant rate and length $n$, this algorithm essentially performs a quantum search which, at each iteration, solves a linear system of dimension $\mathcal{O}(n)$. The typical code lengths used in post-quantum public-key cryptosystems range from $10^3$ to $10^5$. Gaussian elimination, which was used in previous works, needs $\mathcal{O}(n^2)$ space to represent the matrix, resulting in millions or billions of (logical) qubits for these schemes. In this paper, we propose instead to use the algorithm for sparse matrix inversion of Wiedemann (IEEE Trans. inf. theory 1986). The interest of Wiedemann's method is that one relies only on the implementation of a matrix-vector product, where the matrix can be represented in an implicit way. This is the case here. We give two main trade-offs, which we have fully implemented, tested on small instances, and benchmarked for larger instances. The first one is a quantum circuit using $\mathcal{O}(n)$ qubits, $\mathcal{O}(n^3)$ Toffoli gates like Gaussian elimination, and depth $\mathcal{O}(n^2 \log n)$. The second one is a quantum circuit using $\mathcal{O}(n \log^2 n)$ qubits, $\mathcal{O}(n^3)$ gates in total but only $\mathcal{O}( n^2 \log^2 n)$ Toffoli gates, which relies on a different representation of the search space. As an example, for the smallest Classic McEliece parameters we estimate that the Quantum Prange's algorithm can run with 18098 qubits, while previous works would have required at least half a million qubits.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in ASIACRYPT 2024
Keywords
Prange's AlgorithmQuantum SearchInformation Set DecodingQuantum Cryptanalysis
Contact author(s)
clemence chevignard @ inria fr
pierre-alain fouque @ irisa fr
andre schrottenloher @ inria fr
History
2024-09-10: revised
2024-06-06: received
See all versions
Short URL
https://ia.cr/2024/907
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/907,
      author = {Clémence Chevignard and Pierre-Alain Fouque and André Schrottenloher},
      title = {Reducing the Number of Qubits in Quantum Information Set Decoding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/907},
      year = {2024},
      url = {https://eprint.iacr.org/2024/907}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.