An uncertain path to quantum supremacy: Notes from RSA

Uncertainty. That’s the best word to describe the feeling I had roaming around the halls of RSA Conference 2018, taking part in sessions focused on quantum computers and perceived dangers for cybersecurity. I was not alone. The traditional cryptographers’ panel of the opening keynote listed the “rise of quantum computing power” as one of the threats to the cybersecurity industry. But there were no real estimates of when it would finally happen. Let’s try to connect some dots from different areas and collapse the wave function of knowledge, distributed among tracks, into some sort of understanding.

Uncertainty, so common for quantum mechanics, is something that we try to avoid in our ordinary and business lives. The normal reaction of an average human to uncertainty is fear. There was no lack of fear expressed by industry representatives that one day all of their encrypted data would become vulnerable to quantum computing. And their fear is not unfounded — all because of quantum supremacy.

You might already have heard the term, which describes a hypothetical state of technology maturity at which quantum computers can perform tasks that classical computers cannot. One such task (not critical to science, but very important to industry) is factoring prime numbers from their product, an operation that is asymmetric in terms of computing power. The task takes little time to check (by multiplying numbers) but an enormously long time to figure out the factors — a point on which pretty much all current encryption schemes rely.

However, the quantitative definition of the term quantum supremacy is relatively fresh, and it doesn’t get much better than what you’ll find in this Nature Physics article. Nature Physics editors estimate that the threshold number of qubits — the point at which the quantum supremacy can be achieved — is approximately 50 qubits. That said, the 72-qubit Google Bristlecone, unveiled a month ago, should be able to beat the world’s best known supercomputer at factoring prime numbers from the result of their multiplication. So, should we be worried?

Well, yes and no. Welcome to the new quantum reality, where no one is certain about the state of things — it’s “yes” and “no” at the same time. Just kidding: The answer is “yes” if you or your clients store encrypted information for long periods of time, and “no” if you don’t.

But how long is “long”? Really, how much time do we have to prepare ourselves? The answer is different for different types of algorithms. During his talk at RSA, Konstantinos Karagiannis, CTO of Security Consulting, BT Americas, estimated that symmetric algorithms (DES, AES) with 512-bit key lengths will fall first, when the number of qubits surpasses 100, allowing them to factor 512-bit messages in minutes. Asymmetric algorithms (RSA, for example) with 4096-bit keys will require 1000-plus qubits to crack in a similar time frame.

As you can see, even the Bristlecone is not there yet. But it may get there next year, if we assume that Moore’s law applies to quantum computers as well. Under that assumption, counting from March 2018 we may forecast that symmetric encryption with 512-bit keys might finally get breached by a hypothetical 144-qubit Bristlecone descendant sometime in late 2019. The asymmetric encryption with 4096-bit keys, then, stays good until six years later, which gives us time until late 2025, when the 1152-something quantum chip might make its debut. That’s a very hypothetical time frame that doesn’t include the adoption of new technology, which is never instant. And, unfortunately, there are no means to verify this forecast; even today’s most powerful supercomputers cannot emulate their quantum counterparts with such large qubit specs.

But at least we have some time estimates for planning ahead. If you don’t plan to keep encrypted data longer than that, you don’t have to worry — international or local regulators will have to come up with quantum-resistant algorithms before 2025. Which, by the way, means either not encrypting data at rest (which might be a bad idea), or doing regular maintenance on stored data, including decrypting and re-encrypting it with stronger algorithms every so often.

If you don’t want to wait until international or local regulators come up with quantum-proof standards, you may want to apply hybrid technology — a combination of existing top-notch cryptography technologies like RSA, with proper-length keys, and, for example, algorithms based on elliptic curves (ECC). The first cannot be decrypted with classical methods, and the second is presumed to be quantum-resistant, although it can be broken with modern computers. The combination may be enough to keep your data safe, at least while getting better prepared for the looming quantum computing future. Meanwhile, it is good to monitor advances in the encryption industry and adopt new algorithms as soon as they become available (and proven to be quantum computer resistant).

Other technologies also rely on the asymmetrical nature of digital computing, with blockchain being the biggest potential victim of quantum hacking. So far, only Ethereum has publicly announced a road map to “becoming quantum-resistant.” But did I forget to mention that the one-time pad (a classical method invented in 1882) has built-in invulnerability to quantum hacking? Powered by quantum-key-distribution fiber optics solutions, which are already available to midsize and large companies, it may also become a viable option in a time of collapse uncertainty. And maybe even beyond. We’re uncertain, you know.