There’s a lurking fear in cryptocurrency communities about quantum computing. Could it break cryptocurrencies and the encryption that protects them? How close might that be? Do the headlines around “quantum supremacy” mean that my private keys are at risk?
The simple answer: no. But let’s dive deeper into this phenomenon and really try to understand why this is the case and how quantum computing will interact with cryptocurrencies.
To start off with, let’s define quantum computing and the classical computing we’re all used to, and seeing where the terms compare and contrast with one another. Quantum computing can be roughly placed in the same paradigm as “classical” pre-1900s physics and “modern” physics which comprises Einstein’s insights on relativity and quantum physics.
Classical computing is the kind of computers we’ve grown used to, the extensions of Turing’s theories on computation, the laptops or mobile phones that you carry around with you. Classical computing relies heavily on the manipulation of physical bits — the famous 0s and 1s.
Quantum computing relies on qubits, bits that are held in superposition and use quantum principles to complete calculations. The information captured or generated by a quantum system benefits from the ability of qubits to be in more than one physical state at a time (superposition), but there is information decay in capturing the state of the system.
One point that will be immediately relevant to the discussion is that quantum computers are not universally better than classical computers as a result. When people speak about “quantum supremacy”, including reports from Google GOOG and/or China, they really mean that a quantum computer can do a certain task better than classical computers, perhaps one that is impossible to do in any reasonable timeframe with classical computers.
MORE FOR YOU
We can think of this in terms of time scales from a computing perspective — there are some, but not all functions, that go from being impossible to accomplish in any meaningful human-level time period to ones that become slow but manageable with a large enough quantum computer.
In a way, you can think of Turing tests and quantum supremacy tests in much the same way. Designed at first to demonstrate the superiority of one system over another (in the case of Turing tests, artificial language generation vs. human language comprehension, in the case of quantum supremacy tests, quantum computing systems vs classical computers), they’ve become more gimmick than substance.
A quantum computer has to perform better at some minute and trivial task that might seem impressive but completely useless — in much the same way a Turing test of machine-generated English might fool a Ukrainian child with no fluency in the language.
This means that we have to narrow down to a function that quantum computers can be better on that would materially affect cryptocurrencies or the encryption they’re built on in order for “quantum supremacy” to matter.
One area of specific focus is Shor’s Algorithm, which can factor large prime numbers down into two smaller ones. This is a very useful property for breaking encryption, since the RSA family of encryption depends on factoring large prime numbers in exactly this manner. Shor’s Algorithm works in theory with a large enough quantum computer — and so it’s a practical concern that eventually, Shor’s Algorithm might come into play and among other things, RSA encryption might be broken.
On this front, the US National Institute of Standards and Technology (NIST) has already started gathering proposals for post-quantum cryptography, encryption that would operate and not be broken even with much larger quantum computers than the ones we’re currently able to build. They estimate that large enough quantum computers to disrupt classical encryption will potentially arrive in the next twenty years.
For cryptocurrencies, a fork in the future that might affect large parts of the chain, but it will be somewhat predictable — there is a lot of thought being placed on post-quantum encryption technology. Bitcoin would not be one of the first planks to fall if classical encryption were suddenly broken for a number of reasons. Yet, a soft fork (as opposed to a hard one) might be enough to help move crypto-assets from suddenly insecure keys to secure post-quantum encryption.
Even an efficient implementation of Shor’s Algorithm may not break some of the cryptography standards used in bitcoin. SHA-256 is theorized to be quantum-resistant.
The most efficient theoretical implementation of a quantum computer to detect a SHA-256 collision is actually less efficient than the theorized classical implementation for breaking the standard. The wallet file in the original Bitcoin client is using SHA-512 (a more secure version than SHA-256) to help encrypt private keys.
Most of the encryption in modern cryptocurrencies are built on elliptic curve cryptography rather than RSA — especially in the generation of signatures in bitcoin which requires ECDSA. This is largely due to the fact that elliptic curves are correspondingly harder to crack than RSA (sometimes exponentially so) from classical computers.
Thanks to Moore’s law and better classical computing, secure RSA key sizes have grown so large so as to be impractical compared to elliptic curve cryptography — so most people will opt for elliptic curve cryptography for performance reasons for their systems, which is the case with bitcoin.
However, quantum computers seem to flip this logic on its head: given a large enough quantum computer with enough qubits, you can break elliptic curve cryptography easier than you might break RSA.
Both elliptic curve cryptography are widely used in a bunch of other industries and use cases as well — RSA-2048 and higher are standards in the conventional banking system to send encrypted information, for example.
Yet, even with a large enough quantum computer, you would still have to reveal or find somebody’s public keys so they could be subject to attack. With cryptocurrency wallet reuse being frowned upon, and a general encouragement of good privacy practices, the likelihood of this attack is already being reduced.
Another area of attack could be Grover’s algorithm, which can exponentially speed up mining with a large enough quantum computer — though it’s probable that ASICs, the specialized classical computers mostly used to mine bitcoin now, would be faster compared to the earliest versions of more complete quantum computers.
This poses more of a stronger threat when it comes to the state of cryptocurrencies: the ability to mine quickly in a sudden quantum speedup could lead to destabilization of prices and more importantly control of the chain itself — an unexpected quantum speedup could, if hidden, lead to vast centralization of mining and possible 51% attacks. Yet the most likely case is that larger systems of quantum computing will be treated like any kind of hardware, similar to the transition for miners between GPUs, FGPAs and ASICs — a slow economic transition to better tooling.
It’s conceivable that these avenues of attack and perhaps other more unpredictable ones might emerge, yet post-quantum encryption planning is already in process — and through the mechanism of forks, cryptocurrencies can be updated to use post-quantum encryption standards and defend against these weaknesses.
Bitcoin and even other cryptocurrencies and their history are filled with examples of hardware and software changes that had to be made to make the network more secure and performant — and good security practices in the present (avoiding wallet reuse) can help prepare for a more uncertain future.
So quantum computers being added to the mix won’t suddenly render classical modes of encryption useless or mining trivial — “quantum supremacy” now doesn’t mean that your encryption or the security of bitcoin is at risk right at this moment.
The real threat is when quantum computers become many scales larger than they currently are — by which point planning for post-quantum encryption, which is already well on the way would come to the fore, and at which point bitcoin and other cryptocurrencies can soft fork — and use both decentralized governance and dynamism when needed in the face of new existential threats to defeat the threat of “quantum supremacy”.