Ye Olde asymmetric encryption looks like it can beat the coming of the quantum cats
While it’s reasonable to assume that a world with real quantum computers will ruin traditional asymmetric encryption, perhaps surprisingly hash functions might survive.
That’s the conclusion of a group of boffins led by Matthew Amy of Canada’s University of Waterloo, in a paper at the International Association of Cryptologic Research.
The researchers – which included contributions from the Perimeter Institute for Theoretical Physics and the Canadian Institute for Advanced Research – looked at attacks on SHA-2 and SHA-3 using Grover’s algorithm (a quantum algorithm to search “black boxes” – Wikipedia).
They reckon both SHA-256 and SHA3-256 need around 2166 “logical qubit cycles” to crack.
Perhaps counter-intuitively, the paper says the problem isn’t in the quantum computers, but the classical processors needed to manage them.
The paper notes: “The main difficulty is that the coherence time of physical qubits is finite. Noise in the physical system will eventually corrupt the state of any long computation.”
“Preserving the state of a logical qubit is an active process that requires periodic evaluation of an error detection and correction routine.”
If the quantum correction is handled by ASICs running at a few million hashes per second (and if Vulture South’s spreadsheet is right), Grover’s algorithm would need about 1032 years to crack SHA-256 or SHA3-256.
That’s considerably longer than the mere 14 billion years the universe has existed, although less than the estimated 10100 years until the heat death of the universe.
Even if you didn’t care about the circuit footprint and used a billion-hash-per-second Bitcoin-mining ASIC, the calculation still seems to be in the order of 1029 years. ®