Quantum computers could crack Bitcoin, but fixes are available now

Shor, we need a new sig scheme

By Richard Chirgwin


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. ®

Sign up to our NewsletterGet IT in your inbox daily


More from The Register

Keen for much-hyped quantum computing to finally land? Don't expect it for a decade

Uncle Sam says it has no clue when the complex tech will arrive in a useful form

Microsoft ports its Quantum Development Kit to Linux and macOS

Now that it's not Windows-only, you can simulate a theoretical computer on a real computer

Google, Volkswagen spin up quantum computing partnership

Pair to work on traffic optimisation and better batteries

Boffins manage to keep graphene qubits 'quantum coherent' for all of 55... nanoseconds

Doesn't sound very long, but it could have big implications for quantum computing

Net's druids thrash out specs for an independent IETF

This matters because right now there's no formal structure, which makes things tenuous

'Quantum supremacy will soon be ours!', says Google as it reveals 72-qubit quantum chip

Don't panic: 'supremacy' is the point at which quantum kit trumps classical computers

Microsoft asks devs for quantum leap of faith

Try writing quantum code in Q#, because...uh, teleportation

If you've been dying to run some math on a dinky toy quantum computer, IBM may have something for you

Well, we all have to start somewhere: Rentable Q machine has just 20 qubits

Alibaba fires up a cloudy quantum computer

Five-qubit creation is behind the great firewall and outside it at the same time!

Quantum, Linux and Dynamics: That's the week at Microsoft, not a '70s prog rock band

Roundup Sorry to disappoint