Paper 2024/907
Reducing the Number of Qubits in Quantum Information Set Decoding
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 postquantum publickey 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 matrixvector product, where the matrix can be represented in an implicit way. This is the case here. We give two main tradeoffs, 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)
 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
pierrealain fouque @ irisa fr
andre schrottenloher @ inria fr  History
 20240910: revised
 20240606: received
 See all versions
 Short URL
 https://ia.cr/2024/907
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/907, author = {Clémence Chevignard and PierreAlain 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} }