Has the quantum crypto break already happened?

Better quantum algorithms and a strange silence since last year from quantum computing researchers suggest that we are closer to breaking traditional encryption than most people believe.

Encrypted blocks of multicolored data cubes rolling out.
Matejmo / Getty Images

I believe that quantum computers are probably being used now to break today’s encryption secrets. I’m not normally a conspiracy theorist, so let me tell you why I think this is true.

Ever since Peter Shor released a quantum algorithm in 1994 that proved quantum computers with enough quantum bits (qubits) could easily break most popular public key cryptography (e.g., RSA, Diffie-Hellman, Elliptic Curve), we’ve all been waiting for the day when that occurs. It’s generally known as the “quantum crypto break.”

Quantum computing experts didn’t know when it might occur, but they felt that it was around 10 years away. Today, more people think that the quantum crypto break is less than 10 years away, and perhaps only a few years away. Indeed, the most knowledgeable government agencies that deal with setting national cryptography standards believe that now is the time to start preparing for the quantum crypto break. They haven’t shared that the quantum crypto break has happened or when it will occur, only that it’s close enough that we need to start moving to quantum-resistant cryptography.

When I started writing my book, Cryptography Apocalypse, regarding quantum computers and how to prepare for the coming quantum crypto break, I believed it was only a few years away. By the time I finished writing it six months later, I started to think that the quantum crypto break has likely happened.

What needs to happen for the quantum crypto break to occur

For the quantum crypto break to occur, four things need to happen. At least three have happened and only the timing of the last one is being questioned.

1. Quantum mechanics must be real

Quantum mechanics has been known about for over 100 years, but it is full of seemingly strange and contrarian laws (such as “spooky” entanglement, superposition, and the observer effect). Despite growing and overwhelming evidence, the brightest minds could not fully believe it. Albert Einstein spent many years trying to disprove it and died believing it wasn’t true. In 1972 and again in 1981, conclusive experiments confirmed the soundness of quantum physics. Almost no one questions the realness of quantum physics today.

2. We must be able to make quantum computers

When Shor released his quantum crypto cracking algorithm in 1994, not a single quantum computer existed. Even though quantum mechanics was real, there was a chance we would be unable to harness the quantum properties of subatomic particles.

The first quantum computer was made in 1998. It was only one qubit and quickly increased to two, but it showed that computers that used quantum properties were possible. Over 20 years later, over 100 different quantum computers exist, and thousands of devices work using quantum properties. Hundreds of companies and thousands of scientists are working on improving quantum computers. Nations, including the United States and China, spend billions of dollars each year to make better quantum computers.

3. Quantum computers must be able to break traditional public key crypto

Even though Shor’s algorithm showed that quantum computers could theoretically break most traditional public key crypto, it’s another to show that they can in practice. That changed as soon as we had the first quantum computers.

One of the first things researchers did with quantum computers to test Shor’s algorithm. It was successful but used very small prime numbers (three and five) to factor another small number, 15. It proved that Shor’s algorithm worked in the way he said it would on quantum computers.

4. We need enough error-free qubits

The last remaining potential block having enough error-free qubits to factor large prime number products, which are the central protection in most of today’s traditional public key crypto. A quantum computer must have double (plus two to three) qubits more than the number of bits being factored. So, a 2,048-bit asymmetric would take 4,099 qubits to factor, and a 4,096-bit asymmetric key would take 8,195 qubits to factor.

The most powerful publicly known Quantum computers have 70 to 80 qubits, and not so error-free. It is rumored that some of the quantum computers need thousands to hundreds of thousands of other supporting qubits (called ancillary qubits) for every directly computing qubit. That means that that some quantum computers might need millions of qubits to accomplish the quantum crypto break.

We’ve been at 70 to 80 semi-stable qubits going on two years after years of making steady progress. If 70 or 80 qubits is the limit, then the quantum crypto break hasn’t happened. Is it possible that a secret quantum computer team has obtained more stable qubits and has successfully accomplished the quantum crypto break and we just don’t know about it?

3 reasons the quantum crypto break might have happened

Newer algorithms reduce the number of qubits needed. Shor’s algorithm is a ceiling on the number of qubits needed to break large prime number equations. It was the first. Since it was released, several other algorithms have improved on both the speed of the possible quantum crypto break (which was very fast already) and lowered the number of qubits needed. Cryptographic attacks get better and better over time. It’s even possible that someone has created an algorithm that can do it with only 70 to 80 semi-stable qubits, only it takes longer--days instead of minutes.

Making more qubits should be getting easier. The first qubit was the hardest to make. Going from the original quantum mechanic theories in the early to 1900s to the first working quantum computer took almost 100 years. Since then, we’ve gone from one or two qubits in 1998 to 70 to 80 qubits. I don’t understand how if we have dozens of semi-stable qubits that we can’t have a million of them. If there is anything that the US (and China) does well since the days of Henry Ford, it is to take one of something and turn it into a billion of something quickly.

I don’t make this claim lightly or naively. I understand the huge challenges of making any stable qubits at all and how making a million error-prone qubits would only make the same problems seen at smaller levels much worse. Quantum computing scientists around the world are attacking the problem in dozens of ways, ranging from increasing qubit stability, reducing quantum gate times, and decreasing the time a qubit needs to remain stable to finish its task.

I think we know how to make stable qubits. Microsoft has made at least a 1-qubit, very stable quantum computer based on Majorana fermions. All it takes to make more stable qubits is money and resources, and the government is certainly good at that. Microsoft alone has at least eight quantum research centers around the world. I’m supposed to assume that we can’t figure out a way to make more?

Experts are mysteriously silent on quantum computing progress. For many years quantum computing vendors openly discussed how many qubits they had and how many they were soon to have. A website is even dedicated to showing those numbers. I used to go there weekly to see what new numbers were posted. Suddenly, in the middle of 2018, the numbers stopped being regularly increased. Each week that goes by without a new qubit record seems suspiciously strange.

I’ve been talking to and interviewing quantum computing scientists for years, including some working on secret government projects. They used to regularly update me on their progress. They wouldn’t give me any details beyond generalities. I would routinely ask them, “Have we achieved the quantum crypto break?” They would not comment fully or publicly, more than one indicated that they had not. Then in June 2018, all those same people suddenly went silent.

So, as of June 2018, not only did my long-time sources go quiet, but so did the public website showing progress on qubit counts. After making steady progress for years, am I supposed to believe all the different quantum computing teams have hit some technological block toward achieving more stable qubits?

This feels far more like the calm before the storm. There is a good chance that multiple teams have made significant progress, but they are being forced to a vow of secrecy.

I love our government, but the National Security Agency (NSA) and the National Institute of Standards and Technology (NIST), which is in charge of national crypto standards and the move to quantum-resistant ciphers, have a long history of accomplishing significant crypto achievements and keeping us in the dark. Heck, they didn’t reveal that they had obtained asymmetric cryptography a few years before the Diffie-Hellman public declaration in 1976 until a few years ago.

The NSA has the dual objectives of making new crypto achievements, including breaking trusted cryptography, and also protecting us against other nation’s cryptographic achievements. But 90% of its resources are focused on breaking secrets and only 10% on protecting us. Again, when given the chance to better protect us by telling us that they have obtained a cryptographic achievement and keeping it secret so they could use it against their targets, they keep things secret for as long as possible.

It’s hard to have two major, counter objectives and do both perfectly. I believe that if the NSA (or China) had obtained the quantum crypto break, there is no way they would tell anyone else. It would be counter to their primary objective of reading their target’s secrets. You could even say that it would be negligent for them to reach the quantum crypto break and publicly reveal it before they have to.

Once we finally learn the true quantum crypto break timeline, many years from now, we will learn that some government achieved it far earlier than the rest of the world knew. History is replete with this sort of examples.

No, I don’t know for sure if we’ve already achieved the quantum crypto break. It’s probably only three years or less away, but it wouldn’t at all surprise me if it’s already been done. We’ve got quantum mechanics. We’ve got quantum computers. We’ve got qubits. The hardest part has already been done. Getting more stable qubits just doesn’t seem nearly as difficult.