Quantum computers could crack Bitcoin, but fixes are available now

Shor, we need a new sig scheme

By Richard Chirgwin

Posted in Security, 9th November 2017 03:45 GMT

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

10 Comments

More from The Register

Google, Volkswagen spin up quantum computing partnership

Pair to work on traffic optimisation and better batteries

'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 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

Microsoft asks devs for quantum leap of faith

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

Google: We don't have a quantum computer yet, but we have a compiler

It's quantum, it's open source, it's on GitHub. Did we miss anything?

Alibaba fires up a cloudy quantum computer

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

Boffins build a 2D 'quantum walk' that's not a computer, but could still blow them away

Analogue simulation a short-cut to faster computing

Cisco backs test to help classical crypto outlive quantum computers

Borg helps Isara's post-quantum PKI cert test in the hope it future-proofs TLS

I spy with my little eye ... a quantum drum with TRILLIONS of atoms

Boffins: 'infinitely precise' measurements feasible

Parity calamity! Wallet code bug destroys $280m in Ethereum

Punter 'accidentally' borks dozens of strangers' cryptocurrency collections