Quantum Circuits for Information Set Decoding : Quantum Cryptanalysis of Code-Based Cryptosystems
The emergence of quantum computing represents a profound challenge to the security of widely-adopted public-key cryptographic systems, which rely on the computational complexity of tasks such as factoring large integers or solving discrete logarithms. To confront this challenge, esteemed organizations like the U.S. National Institute of Standards and Technology (NIST), the Chinese Association for Cryptologic Research (CACR), and the European Telecommunications Standards Institute (ETSI) are actively engaged in the formulation of cryptographic primitives capable of withstanding both classical and quantum attacks. These novel cryptographic systems, collectively termed post-quantum cryptosystems, are at the forefront of standardization efforts. Among the leading contenders in this standardization endeavor, linear code-based cryptosystems, deriving their strength from the computational complexity of the Syndrome Decoding Problem (SDP), have gained significant recognition. The SDP is defined as the task of retrieving an error vector when provided with the parity check matrix of a randomly generated linear block error correction code and the syndrome of the error, as computed through the same matrix. Classically, the most effective technique for solving the SDP is the Information Set Decoding (ISD) method, which, notably, exhibits exponential complexity with respect to the parameters of the cryptosystems. Current quantum approaches to the SDP, on the other hand, do not surpass the quadratic speedup offered by adapting Grover’s algorithm to the ISD technique, and provide only asymptotic estimates of their computational cost, potentially hiding non-trivial constant and polynomial factors. The central focus of this study revolves around the precise computational complexity evaluation of quantum solvers for the SDP, tailored to cryptography-grade code parameters. Our approach introduces quantum circuits designed for universal quantum gate-based computing models, that are build upon the foundations laid by classic ISD techniques. Our scrutiny extends to both complete quantum solutions to the SDP and hybrid methodologies that effectively partition the computational load between classical and quantum computing resources. In our investigation, the approach stemming from Prange’s approach to the ISD technique stands out, as it displays a substantial enhancement in computational efficiency. Notably, it leads to a reduction in both the depth of quantum circuits and the depth-times-width metric by factors ranging from 2¹² to 2²⁴ applicable to concrete cryptography-grade parameters. Surprisingly, our findings reveal that the gains achieved through the approach inspired by Lee and Brickell’s ideas, which materialize as a hybrid classical-quantum algorithm, are somewhat modest. These enhancements range from 2¹⁰ to 2²⁰ for the same cryptographic parameters, a result contrary to expectations based on classical counterparts, where Lee and Brickell’s approach prevails over Prange’s one. However, the hybrid approach substantially reduces the size and depth of quantum circuits, rendering the estimates more realistic and facilitating parallel execution on separate quantum computing platforms. Our quantitative analysis of computational costs brings forth a significant conclusion: all code-based cryptoschemes under the scrutiny of esteemed organizations such as NIST, particularly BIKE, HQC, and McEliece, unequivocally surpass the predefined threshold for computational hardness. Put simply, they prove to be computationally more demanding than the task of breaking a corresponding symmetric cipher with appropriately-sized key lengths. Furthermore, a critical vulnerability in the Classic McEliece cryptoscheme is unveiled. Parallelizing this algorithm across multiple quantum processing units erodes its security, plunging it below the targeted security threshold by a factor of 16. An ancillary contribution of this research is the development of a set of quantum circuits capable of solving common algebraic and algorithmic problems, including Gauss-Jordan Elimination over finite fields, bit string sorting, and Hamming weight computation, which may be of independent interest in the field of quantum computing.