Yes, Quantum Computers Do Threaten The Future of Bitcoin

Quantum Computers Will Eventually Break Bitcoin’s Blockchain, But That’s Just One Side of the Story

Recently I was asked to contribute a quote to a great article by Dom Galeon at Futurism called “The Future of Bitcoin is Threatened by Quantum Computers.” He posits that blockchain and quantum computing are on a collision course. As quantum computing power increases, quantum computers are a threat to break blockchain’s underlying encryption.  That means they’re a threat to cryptocurrencies like Bitcoin. Dom did an excellent job on this piece. I just want to briefly discuss the other side of the story. Dom’s article is based in part on a new white paper written by Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel entitled “Quantum Attacks on BitcBin, and How to Protect Against Them.”

The Short Version

Here’s the abstract for you crib notes kids:

The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk are cryptocurrencies, a market currently worth over 150 billion USD. We investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.

The Rest of the Story

Note that Aggarwal and his colleagues from the National University of Singapore (NUS) discuss both the threat and the options to defend against it. Blockchain definitely has some vulnerabilities that quantum computers could potentially exploit in the future. However, as I said in a previous post:

Take a deep breath. It’s not the end of encryption. Let’s not scare the masses with horror stories about a technology that will change our world for the better. Why not talk about the potential for new quantum encryption schemes? Or how the power of quantum computers could be used to improve security? Every new technology can be viewed as a double-edged sword. When it comes to security, too many people are only seeing one of the edges.

Critics often overstate the quantum threat to our current encryption schemes. They don’t account for the potential for quantum computers to develop new encryption schemes.  They forget the time we have to prepare for the threat’s arrival.  The quantum future is still bright. Quantum computing will still do far more good than harm. Breaking encryption is only one application for the immense power of quantum computers.  I know the Bitcoin folks have more pressing problems, but I’m betting they’ll come up with a way protect their product in the next ten years.

Any takers?

 

 

  • Austin

    A welcome, authoritative and very appropriately humorous take as well on this topic from UT theoretical computer science professor Scott Aaronson, via his blog “Shtetl-Optimized”:

    “For several years, people have been asking me whether Bitcoin is resistant against quantum attack. Now there’s finally an expert analysis, by Aggarwal et al., that looks into exactly that question. Two-sentence summary: the proof-of-work is probably fine, although Grover’s algorithm can of course be used against it, which might eventually necessitate adjusting the difficulty parameter to account for that, and/or migrating from a pure preimage search task to collision-finding, where my result with Yaoyun Shi showed that quantum computers offer “only” an n2/3 black-box speedup over classical computers, rather than a square-root speedup. The scheme for signing the transactions, which is currently based on elliptic curve cryptography, is the real danger point, but again one could address that by migrating to a post-quantum signature scheme.”

    (And for the punchline:) “My main comment about the matter is that, if I’d invested in Bitcoin when I first learned about it, I’d be rich now.”

    • Austin

      P.S. I would be willing to take your bet, with the expectation on my part that we will see a q-technological surprise that will beat the formation of protective q-encryption. But — also with appropriate humor — if I won, both the dollar and Bitcoin would be destroyed by then, so for the moment I’m unsure as to how to collect my winnings. Perhaps a certain number of goats…?