Paper 2026/1411

Improved Quantum Circuits for Information Set Decoding with Application to Code-Based Cryptography

Abstract

Information set decoding (ISD) is the standard generic decoding attack considered for code-based cryptography. A concrete quantum-resource estimate for Grover-accelerated ISD requires an oracle whose dominant component is Gauss–Jordan elimination. We improve the elimination circuit of Perriello et al. [25] and Jang et al. [15] by not updating the entries that no later pivot or the final weight predicate reads. The required result vector is recovered by a parallel back-substitution on the syndrome register. For the target schemes, our elimination circuit improves the qubit count by about 22% compared to [15]. The Toffoli count improves by about 20% compared to both [25] and [15]. The Toffoli depth improves by about 67% compared to [25] but degrades by about 0.3% compared to [15]. We report logical resource estimates for the quantum ISD attack on HQC and Classic McEliece. The product of the total gate count and the full depth exceeds the NIST post-quantum security thresholds, and the full depth exceeds the MAXDEPTH upper bound. We also provide fault-tolerant estimates of the physical qubit count and the runtime under a surface-code model with magic-state distillation. As one example, HQC-128 requires about $2^{43}$ physical qubits and about $2^{53}$ years at a 1 μs code cycle.