Does Quantum Computing Kill Bitcoin?

Quantum Crypto Is Upon Us

We know it is coming. Probably.

For the last 25 years and more, we’ve known that quantum computing is coming, and that one of its first uses will be code breaking.

Much of the cryptographic infrastructure of the Internet is based on methods that are proven to be so hard to compute that a brute force or guessing attack is “infeasible”. Generally, this means that with current and projected technology, it would take a long time, years or centuries, to work it out.

But quantum computers should be zillions of times faster at certain kinds of computations, including the beating heart of key crypto algorithms. Uh, oh!

This cuts both ways. Quantum encryption might well be unbreakable by conventional computers (good for the defense, bad for the offense). But much of conventional computing and networks will be effectively clear text (bad for defense, good for offense).

I assume the NSA and all the other technically advanced powers are on the case, though I certainly don’t know exactly what is going on. We do know, for example, that there is a public effort in China to deploy quantum cryptography on a backbone network. Google has announced it has the technology. It is likely that high security nets have already got such technology, long before any public announcements. The future is already here.

Mark Kim writes this month in Quanta Magazine about these developments [3]. In particular, he discusses a paper by Bernstein, Daniel J. and colleagues, which looks at “Post Quantum RSA”, i.e., what happens to RSA encryption in a quantum computing world [1].

The thrust of this paper is proposals for “RSA parameters can be adjusted so that all known quantum attack algorithms are infeasible while encryption and decryption remain feasible.” ([1], p. 1)  As they say, their ideas are “not what one would call lightweight cryptography”. The case they analyze involves a 1 Terabyte key! This is expensive and awkward, but the point is that for cases that demand extreme measures (e.g., guarding root keys, critical backbones, and other vital secrets) there may be ways to protect against quantum decryption attacks, even with conventional computing.

This is a cool idea, assuming it bears out. If nothing else, it dilutes the aura of magical invincibility that surrounds quantum cryptography.

But these measures and other possible approaches, don’t really solve the problem for the bulk of the Internet. It may soon be true that well endowed actors, nation states and googles, can crack any crypto they need to.

What Happens to Bitcoin, blockchains, and other Cryptocurrency?

These developments potentially have serious implications for cryptocurrencies and blockchains, all of which depend on cryptography and, equally important, cryptographically-secured systems.

I’m not sure exactly what parts of the Nakamotoan mechanisms might be affected by quantum computing, some might even be improved. But the big two to worry about are the hashing scheme (the basis of ‘mining’) and the ‘addresses’ which are cryptographic public keys. These mechanisms are secured by algorithms that depend on the speed and cost of computing, so a major disruption of speed could breach the entire basis for Bitcoin.

I don’t know if there are ways to subvert the hashing scheme with quantum computing, and I certainly don’t know what the cost/benefit analysis might be for any such scheme. Quantum computing is likely to be more expensive, so who knows when it is cost effective? (Note that the argument that “it’s too expensive to be reasonable” simply does not apply to state actors.)

One potential problem is if it becomes reasonable for some wealthy miners to have systems that are much, much faster, and thereby to accumulate a large fraction of the total hashing power, then that would be a very serious problem.

An even bigger problem is that governments and large companies will soon be able to crack public keys, and therefore probably will be able to mess with Bitcoin addresses. Yoiks! Unfriendlies not only reading your mail, but manipulating your Bitcoins and your “smart contracts”, too. Again, arguments about supposed economic and cost barriers don’t apply to state actors.

Worst of all, anyone actually using Bitcoin or a blockchain for any normal purpose (i.e., other than mining or currency exchange), relies on the general security of the network and nodes. Even if the blockchain, servers, and wallets aren’t cracked (which they will be), the network itself is likely to be unsecure.

It’s hard to know what might happen, but if unfriendlies can insert man-in-the-middle attacks between nodes, then all bets are off. Anyone trying to actually use Bitcoin with a wallet and local connection would be vulnerable in any number of possible ways.

Game over.

Time’s Up For Cryptocurrencies?

The official Bitcoin wiki pages have a short note on “Quantum computing and Bitcoin”, which whistles past the graveyard. They suggest that there is a decade or more to do something, which is probably optimistic. But even this Pollyanna-ish page notes that there aren’t any solid solutions known at this time.

This isn’t great news, especially given Bitcoin’s disfunctional governance system, which has been spinning its wheels for two years over much simpler technical issues. How in the world will the crypto community cope with the existential threat of QC?

Obviously, I’m far more concerned about the collapse of the whole Internet.

Perhaps Bitcoin and other cryptocurrencies might turn out to be canaries in the coal mine, keeling over just before the the big explosion.


  1. Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta, Post-quantum RSA. Cryptology ePrint Archive: Report 2017/351, 2017. https://eprint.iacr.org/2017/351
  2. Bitcoin Foundation. Quantum computing and Bitcoin. 2016, https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin.
  3. Mark H. Kim, Why Quantum Computers Might Not Break Cryptography. Quanta magazine.May 15 2017, https://www.quantamagazine.org/why-quantum-computers-might-not-break-cryptography-20170515

 

Cryptocurrency Thursday

3 thoughts on “Does Quantum Computing Kill Bitcoin?”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s