A Quantum Circuit to Speed-up the Cryptanalysis of Code-based Cryptosystem

The significant interest in cryptographic primitives providing sound security margins when facing attacks with quantum computers is witnessed by the ongoing USA National Institute of Standards and Technology Post-quantum Cryptography Standardization process. Sound and precise evaluation of the amount of computation required to break such cryptographic primitives by means of quantum computers is required to be able to choose the cryptosystem parameters. We present a full description of a quantum circuit to accelerate the computation of the solution of the Information Set Decoding problem , which is currently the best known non-structural attack against code-based cryptosystems. We validate our design running it on small instances of error correction codes, which allowed a complete validation on the AtoS QLM quantum computer simulator. We detail the circuit accelerating the exponential complexity search phase in the Lee and Brickell variant of the ISD solver, and provide its computational complexity for cryptographically relevant parameters taken from the third round candidates in the USA post-quantum standardization process.