An Optimized Quantum Implementation of ISD on Scalable Quantum Resources
This work addresses the security analysis of code-based cryptographic proposals by clarifying the feasibility of quantum attacks, which is crucial for cryptographers and security analysts.
The authors tackled the uncertainty around the practical efficiency of quantum attacks on code-based cryptography by designing the first full quantum circuit for the Information Set Decoding (ISD) algorithm, showing that Prange's ISD can be implemented with only a logarithmic overhead in circuit depth compared to classical methods. They also introduced hybrid classical-quantum trade-offs that allow tailoring qubit usage to available resources while maintaining quantum speedups, overcoming previous optimality results when constraining circuit width.
The security of code based constructions is usually assessed by Information Set Decoding (ISD) algorithms. In the quantum setting, amplitude amplification yields an asymptotic square root gain over the classical analogue. However, it is still unclear whether a real quantum circuit could yield actual improvements or suffer an enormous overhead due to its implementation. This leads to different considerations of these quantum attacks in the security analysis of code based proposals. In this work we clarify this doubt by giving the first quantum circuit design of the fully-fledged ISD procedure, an implementation in the quantum simulation library Qibo as well as precise estimates of its complexities. We show that against common belief, Prange's ISD algorithm can be implemented rather efficiently on a quantum computer, namely with only a logarithmic overhead in circuit depth compared to a classical implementation. As another major contribution, we leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs, that allow to tailor the necessary qubits to any available amount, while still providing quantum speedups. Interestingly, when constraining the width of the circuit instead of its depth we are able to overcome previous optimality results on constraint quantum search.