How close are we to breaking encryption with quantum computing?

Quantum encryption cracking is on its way, so it’s time to start getting ready for it.

When famed Nobel Prize winning physicist Richard Feynmann came up with the concept of quantum computers in 1982 in his speech and paper Simulating Physics with Computers, he probably wasn’t thinking about the effects it would have on cryptography. Today, we face the real possibility of quantum computers overturning the apple-cart of classical encryption and the promise of nigh-unto-unbreakable quantum encryption.

This, not to put too fine a point on it, will change everything.

All encryption, all the time

Considering in today’s world we do everything — from buying our groceries to talking to our friends and family to doing our job — online. The coronavirus crisis is, of course, made that it even pervasive.  And, to do that securely, we rely on encryption. It’s become so commonplace we don’t notice it. For example, thanks largely to Let’s Encrypt, 91 percent of your US web visits are now secured by Transport Layer Security (TLS) encryption.

The Wi-Fi, through which our data flies, is defended by Wi-Fi Protected Access 2 (WPA2). And, these, and every credit-card transaction is protected at heart by Advanced Encryption Standard (AES) encryption. We don’t think about it, we just use it and assume no one will read our work documents, snatch our credit-card numbers, or look over our virtual shoulders to read out email.

Of course, all the encryption methods are under constant assault. For instance, the Wi-Fi security standards of yesteryear — Wired Equivalent Privacy (WEP) and WPA — have all fallen as processors have grown ever faster. The default answer to this eternal problem is to increase the key length.

Generally speaking, the longer the key length the tougher it is for a brute-force attack to crack the encryption. Brute-force attacks are just what they sound like. The attacker tries key after key until one fits. Even so, it would take millions of years using classic computers to brute force it 256-bit AES. I repeat, using “classic computers.”

[ Related: Quantum computing predictions for 2020 ]

Quantum comes in

Quantum computers are another thing entirely. Instead of classic computer’s binary calculation with bits, which can be either 1 or 0, quantum computing uses qubits. These can store much more data because they can exist in a superposition of many possible combinations of 1 and 0 simultaneously. Practically speaking that means several qubits in superposition can parallel process an enormous number of potential outcomes at once. Only at the end of a calculation do the qubits collapse to either 1 or 0.

In addition, pairs of qubits can be “entangled.” That means they exist in a single quantum state. When you change the state of one, the state of the other instantaneously changes no matter the distance between them. How? We don’t know. Einstein, called it “spooky action at a distance,” and we’ve no better guess today. That said, entanglement makes quantum computers even more powerful than classic computers, doubling the bits, from say 32 to 64-bit processors, essentially doubles their processing power. When you double qubit and entangle them you get much more computing ability.

How much more? According to Neven’s law, named after is creator Hartmut Neven, the director of Google’s Quantum Artificial Intelligence lab. Quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate.

That said, quantum computers are difficult to build and have their own problems. The quantum state is as fragile as a snowflake in your bare hand. Any slight variant in temperature or vibration can cause “static,” which leads to “decoherence.” And, once a qubit is in decoherence, its calculation has failed and you must start again.

Error correction can help, but we’re still a long way from being able to use it reliably. The National Academies of Sciences, Engineering and Medicine estimated in December 2019 that the average error rate of qubits “would need to be reduced by a factor of 10 to 100 before a computation could be robust enough to support error correction at scale.”

The answer to this is to use smart quantum algorithms. These are designed to run quantum calculation as fast as possible, so you get answers before the qubit goes into decoherence. You can also improve efficiency by running multiple qubits so that one or more of them last long enough to finish a calculation.

Eventually, we’ll have quantum computers that can achieve quantum supremacy. That is to say when quantum computers can complete a mathematical calculation faster than even the most powerful classical supercomputer. Or, if it can make calculations that a supercomputer can’t accomplish at all.

We may, or may not, already be there. Google claims that it’s 54 qubit Sycamore quantum computer reached quantum supremacy last fall. IBM, another major quantum computer power, suspects Google really hasn’t succeeded yet. In any case, we’ll soon reach that point. And, what does that mean for encryption? Let’s see.

Cracking the uncrackable

All the way back in 1994, mathematician Peter Shor discovered a quantum algorithm, Shor’s algorithm that could crack some encryption codes like RSA (Rivest–Shamir–Adleman). Soon thereafter, in 1996, Lov Grover came up with Grover’s algorithm, which can be used to crack AES.

But, our current generation of quantum computers have too much decoherence to allow either method to succeed. Researchers, in 2015, estimated it would take a billion-qubit computer to crack RSA-2048. But, then, in 2019, Craig Gidney and Martin Ekerå showed you could break RSA-2048 encrypted messages with a 20-million qubit computer using a revised algorithm. 

That’s still a lot more than today’s quantum-based computers. D-Wave, claims its Advantage System with Pegasus topology, has more than 5,000 qubits. But, D-Wave uses a method called quantum annealing so it’s qubits aren’t the same as others. It’s comparing apples and oranges. While Google has its 54-qubit Sycamore processor and IBM has commercialized its IBM Q System One with 53-qubits. We’re a long way from breaking conventional encryption, but how far away are we really? Neven’s Law, if it proves true, promises us we’re going to see enormous improvements and it won’t be long.

 Vadim Lyubashevsky, IBM Research cryptography researcher, isn’t overly optimistic. Lyubashevsky said, “At the current rate of progress, it will probably be a couple of decades until we can build a powerful-enough quantum computer. There are currently too many unknowns to give any sort of precise estimate of when such quantum computers will exist.”

He’s not the only one to see it that way. Jake Farinholt, lead scientist on Booz Allen’s quantum computing research team, remarks, “Quantum computers will need to be many, many times larger in capacity than what’s now available. There are numerous technical and engineering challenges that will need to be overcome to get to this scale. While the speed at which advancements are being made is impressive, it is safe to say that crypto-breaking quantum computers are still a ways off.”

Others aren’t so sure. Richard Williamson, senior member of technological staff at security company Utimaco, said, “From a cybersecurity perspective, quantum computing promises to completely upend data security as we know it, rendering current encryption algorithms useless. Quantum computing’s potential to radically shorten the timescale of attacks could, in the hands of a malicious actor, enable cyberattacks unlike anything previously seen.”

Williamson continues, “Four years ago when Utimaco was talking about quantum computing, we were told “Oh, that’s still 20-30 years away.” Three years ago it was “10-20” years. Last year it was “5-10.” This year at conferences people are coming up to the booth and saying ‘oops, we should have been talking about this years ago.’

Related: Experts split on how soon quantum computing is coming

John Prisco, CEO of Quantum Xchange, a company already working on commercializing quantum encryption, reminds us that, “This is not a question of if but rather when. The obstacles needed to overcome current limitations in quantum computing however are non-trivial and we are at least three years away from a quantum computer factoring Shor’s algorithm.”

Still Mark Zhandry, senior scientist in the CIS Lab at NTT Research and an assistant professor at Princeton University, believes “With Google’s recent quantum breakthrough, you could say that we have entered the vacuum tube era of quantum computing. Such computers do not have the scale nor the accuracy to pose a threat to current encryption schemes. It took a couple decades between the development of vacuum tube computers and the emergence of transistor computers; a similar timescale might be reasonable for quantum computers.”

But that doesn’t mean you can relax, Lyubashevsky said. “The real danger to security today is that someone can store your encrypted data and then decrypt it when such a quantum computer does exist. So, if there is something being encrypted now, and someone deems it interesting enough to harvest, then there is a very good chance that it will be decrypted in the future.”

Rodney Joffe, security CTO at Neustar, reminds us, “From a cybersecurity perspective, quantum computing promises to completely upend data security as we know it, rendering current encryption algorithms useless. Quantum computing’s potential to radically shorten that timescale could, in the hands of a malicious actor, enable cyberattacks unlike anything previously seen.” Like what?

Lyubashevsky says asymmetric crypto — in particular elliptic curve cryptography (ECC) — will be the first to be broken by a quantum computer running Shor’s algorithm. That’s important because most crypto-currencies, including market leading Bitcoin and Ethereum, use ECC.

Shielding tomorrow’s data

The National Institute of Science and Technology (NIST) is working with industry partners on “quantum-safe” encryption protocols. Some, like the cryptographic suite, Cryptographic Suite for Algebraic Lattices” (CRYSTALS), which includes Kyber, a key-encapsulation mechanism and Dilithium, a strongly secure digital signature algorithm. has already been submitted to the NIST post-quantum cryptography project. CRYSTALS is available as open-source software from OpenQuantumSafe.org.

Janet Jones, Microsoft’s senior security program manager of customer security & trust engineering, thinks we should “inventory and understand where, what, and why encryption is being used for existing platforms and services.” That done, we should then determine how to build in crypto-agility, the ability to switch to alternative cryptographic methods without making significant changes to the system’s infrastructure.

That won’t be easy or cheap. Utimaco’s chief strategy officer Malte Pollmann, said it “will still take some years before we have a well-proven and tested set of new post-quantum cryptographic-algorithms. And they have a cost — either in terms of processing requirements or storage for key and signature sizes. The good news is that customers and industries can start testing those in their software and products today.”

Zhandry says, “We actually already have quantum-safe encryption algorithms, but they are not widely used yet. One issue is that these new algorithms are still going through the standardization process. Such standardization is necessary so that everyone is on the same page in terms of what algorithm to use.”

What it boils down to is quantum computing will break much, but not all of our current encryption methods. But, there’s no reason to panic yet. Unless you’re got your retirement funds tied up in Bitcoin — then, I’d be a bit concerned.

There is, however, a reason to start working on your post-quantum computer security needs. Quantum computing will crack our current cryptography methods more than soon enough. Far better to be ready than see your secrets vanish in qubit smoke.