Quantum computers could crack Bitcoin, but fixes are available now
Shor, we need a new sig scheme
An international group of quantum boffins reckons Bitcoin could be broken by the year 2027.
The researchers from Singapore, Australia and France say that scenario represents the worst case, and would see a quantum computer able to run Shor's algorithm against the cryptocurrency's protective elliptic curve signature quicker than the 10 minutes Bitcoin needs to record a transaction in the blockchain.
There are two items of good news in the paper for Bitcoin: its proof-of-work isn't as vulnerable to “quantum speedup” as people think, and the signature can be replaced with something more quantum-resistant before the day of reckoning.
In their paper, which landed at arXiv in late October, Divesh Aggarwal and his collaborators say ASIC-based mining rigs are fast compared to even optimistic theoretical quantum computer clock speeds.
A Grover search could work against Bitcoin's “hashcash” proof-of-work, they write, but it would be slow:
The extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speedup, at the current difficulty level, giving quantum computers no advantage. Future improvements to quantum technology allowing gate speeds up to 100GHz could allow quantum computers to solve the PoW about 100 times faster than current technology.
As far as defeating hashcash goes, the numbers are daunting for quantum computer designers: by 2028, the researchers reckon, you'd need a 4.4 million qubit machine to achieve 13.8 gigahashes per second: “This is more than one thousand times slower than off the shelf ASIC devices which achieve hash rates of 14TH/s”.
Shor's algorithm, a quantum algorithm for factoring integers (that's how it would attack cryptography), is a better path, they write.
Deploying a quantum computer against the secp256k1 elliptic curve Bitcoin uses is much more dangerous: if the signature is cracked, the scheme is completely insecure, and attackers can plant fake transactions and steal Bitcoin.
As with cracking the proof-of-work, the researchers assume quantum computers get big and fast relatively quickly, and even so, they fall slightly short: with a 10 GHz clock rate, around half a million qubits, and a low enough error rate of 10-1 could crack the signature in 30 minutes.
That's close enough to make Bitcoin's critical 10-minute rate “highly insecure”, so the authors recommend the Bitcoin protocol be migrated to a post-quantum signature scheme. ®