Over the past few decades, we have seen almost unimaginable progress in computation speed and power. A watch today is a more powerful computer than the first Macintosh that my parents bought me in 1984 (I was very lucky). The weakest and lightest laptop today is more powerful than the computers that I programmed on during my undergraduate studies in university. Do you remember the days of computers with 64 kilobytes of RAM? Now we count in gigabytes and, soon, terabytes.
Yes, I know that I’m old (but at least I’m not reminiscing about punch cards and vacuum tubes), but that’s not really the point. The point is to understand where all of these extremely fast advancements in computing power came from.
The answer is a combination of Moore’s law (stating that the number of transistors on a chip doubles every two years, although this has now slowed down), together with many architectural improvements and optimizations by chip manufacturers. Despite this, the basic way that our most powerful computers work today is the same as in the 1970s and 1980s. Thus, although improvements are fast and impressive, they are all in the same playing field.
Quantum computing is a completely different ball game. Quantum computers work in a radically different way and could solve problems that classical computers won’t be able to solve for hundreds of years, even if Moore’s law continues. Stated differently, quantum computers don’t follow the same rules of classical computing and are in a league of their own. This does not mean that quantum computers can solve all computationally hard problems. However, there are problems for which quantum computers are able to achieve extraordinary speedups.
Some of these problems are closely related to much of modern cryptography, and include the number factorization problem that lies at the core of the RSA cryptosystem, and the discrete log problem that lies at the core of Diffie-Hellman, ECDSA, EdDSA and other cryptosystems (as used in cryptocurrencies and blockchains).
The big question that still has not been answered, despite what you may have read, is whether or not such quantum computers will ever be built. I want to stress that this is still an “if” and not a “when.” The fact that small quantum computers have been built does not mean that quantum computers at the scale and accuracy needed to break cryptography will ever be built. The problems that need to be overcome are considerable. I am not saying that I don’t think they will succeed; I’m just saying that it’s not a certainty.
The next big question is: When will such a computer that is powerful enough to break RSA or ECDSA be built? Or maybe more relevant — when do we have to start worrying about this possibility? I personally believe that this is many years away (I will say at least a decade, but I think it will be more like two decades at least).
Recently, Google’s scientists hailed what they believe is the first demonstration of quantum supremacy. This was widely understood to mean that quantum computers are now already faster than classical ones. And if this is the case, then modern cryptography may be broken very soon, in contrast to the time span that I predicted above.
However, this claim by Google’s scientists needs to be understood in context. “Quantum supremacy” is a technical term used by the academic community to mean when a quantum computer can do just one thing faster than a classical computer. However, this is really not what we think about when we hear “supremacy,” nor is it really relevant to cryptography and other application domains. In particular, what we are really interested in knowing is when quantum computers will be able to solve hard, important problems faster than classical computers, and when quantum computers will be able to break cryptography.
Whether or not quantum supremacy was even demonstrated is not absolutely clear (see IBM’s response). However, in any case, this quantum computation has no effect whatsoever on cryptography, blockchains and cryptocurrencies.
So, what does this mean concretely for us as a community? First, we should rest assured that the cryptographic world is getting ready for any eventuality. In particular, we already have good candidates for post-quantum secure public-key encryption and digital signature schemes, and NIST is working on standardization now. As such, we will not be surprised and unprepared if post-quantum computers that threaten our cryptographic infrastructure become close to reality.
This does not, however, mean that our actual products and software in use are ready for the post-quantum era, and this is often a really hard problem. The solution to this problem is called crypto agility, and it relates to the ease (or lack thereof) with which cryptosystems can be replaced in existing deployed systems.
There are two main aspects to crypto agility. The first is how easily it is possible to change code so that one cryptosystem is replaced with another. The more the specific structure of the cryptosystem is relied upon in the code, the harder it will be to replace. The second is how to make this change while preserving backward compatibility and without introducing new vulnerabilities that can happen when new and old versions operate concurrently.
These are (security) software engineering considerations, and there is no general right answer. However, asking your software team what the cost would be to swap out their crypto is a really important first step.
The good thing about becoming more crypto-agile is that, even if the threat of quantum computing to cryptography never eventuates, it is still a good investment. Cryptosystems, key sizes, modes of operation and more change over time. This is a fact of life and will not change. Being more crypto-agile will enable you to respond faster to such changes and to be ahead of the market when new cryptography is introduced (whether it be for classic security systems or for cryptocurrencies and blockchains). That is always a good thing!
This is an op ed contribution by Professor Yehuda Lindell. Views expressed are his own and do not necessarily reflect those of Bitcoin Magazine or BTC Inc.
The post Op Ed: Quantum Computing, Crypto Agility and Future Readiness appeared first on Bitcoin Magazine.
