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

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 iterate, 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 propose 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.

Available format(s)
Attacks and cryptanalysis
Publication info
Prange's AlgorithmQuantum SearchInformation Set DecodingQuantum Cryptanalysis
Contact author(s)
clemence chevignard @ inria fr
pierre-alain fouque @ irisa fr
andre schrottenloher @ inria fr
2024-06-06: approved
2024-06-06: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.