Resource Estimation of Fault Tolerant Quantum Information Set Decoding

With the ever-present threat of quantum computing looming over the world of cryptography, researchers have been investigating how best to replace existing cryptographic schemes with those that can withstand quantum attacks. Our research contributes to the area of resource estimation, a field concerned with analysing the amount of real-world resources (both temporal and spatial) required for a quantum computer to compromise a given cryptographic scheme using the best known current methods. We present a circuit to perform Prange’s algorithm, a variant of quantum information set decoding. We embed our construction within an error-correction scheme in order to calculate the overhead costs incurred by fault-tolerance. Our analysis shows that current proposed parameters for code-based cryptography provide a much larger security margin than required for their specified security level, and as such could be reduced to improve performance whilst still ensuring quantum immunity.