Improving the Efficiency of Quantum Circuits for Information Set Decoding

The NIST Post-Quantum standardization initiative, that entered its fourth round, aims to select asymmetric cryptosystems secure against attacker equipped with a quantum computer. Code-based cryptosystems are a promising option for Post-Quantum Cryptography (PQC), as neither classical nor quantum algorithms provide polynomial time solvers for its underlying hard problems. Indeed, to provide sound alternatives to lattice-based cryptosystems, NIST advanced all round 3 code-based cryptosystems to round 4. We present a complete implementation of a quantum circuit based on the Information Set Decoding (ISD) strategy, the best known one against code-based cryptosystems, providing quantitative measures for the security margin achieved with respect to the quantum-accelerated key recovery on AES, targeting both the current state-of-the-art approach and the NIST estimates. Our work improves the state-of-the-art, reducing the circuit depth from 2¹⁹ to 2³⁰ for all the parameters of the NIST selected cryptosystems. We further analyse recently proposed optimizations, showing that the overhead introduced by their implementation overcomes their asymptotic advantages. Finally, we address the concern brought forward in the latest NIST report on the parameters choice for the McEliece cryptosystem, showing that the parameter choice yields a computational effort which is slightly below the required target level