Root Causes 37: Quantum Apocalypse - Will Quantum Annealing Break Cryptography?

Hosted by

Fellow

Original broadcast date

September 10, 2019

Quantum annealing is a special case of quantum computing for which the engineering challenges are lessened - and therefore we expect computers of this sort to achieve stability sooner. In this episode we examine the potential for the quantum annealing approach to break RSA-based cryptography sooner than most people have been expecting, and the difficulty of predicting the "Z date" at all.

Podcast transcript

Lightly edited for flow and brevity.

TCTim CallanWe have been talking about quantum computers, which are a threat to encryption, what needs to happen to address the Quantum Apocalypse, and the progress that’s being made by NIST and cryptographers. Today we’re talking about a new development in the space which is called quantum annealing. Jay, what is quantum annealing?

Jason SorokoQuantum annealing’s actually a special case of quantum computing, and it’s a little different. It’s meant to solve a different class of problem. Have you ever heard of a company out of Vancouver, Canada called, D-Wave?

TCTim CallanI have, as it happens.

Jason SorokoI think a lot of people have, if you’ve been searching or just reading general tech journalism. They’re an interesting case where their quantum computing is actually a form of quantum annealing. Not a universal quantum computer.

TCTim CallanHelp me understand the difference between the two. I think we all know what a quantum computer is, at least at a high level. You have these qubits which work differently than a 1/0 gate in that they can have multiple states at once. As such they have the potential to be faster and to solve certain specific computing needs much more efficiently. What is that compared to quantum annealing?

Jason SorokoThere is some underlying quantum physics underneath all this. I think that’s out of the scope of this conversation. We’re going to keep at a higher level and then bring it back to why this is important for cryptographic algorithms and quantum resistant stuff that we’ve been talking about recently, Tim.

TCTim CallanYeah, this is a PKI podcast not a particle physics podcast so let’s make sure we gear it at the appropriate level for that.

Jason SorokoQuantum annealing is trying to harness the natural evolution of quantum states. It’s not trying to do things like manipulate them or try to keep them stable for really long periods of time. That’s the fundamental challenge of a universal quantum computer because a universal quantum computer is really trying to work like a gate model quantum computer.

You’re trying to change states and control the changes of the states of the underlying quantum mechanism, and that’s difficult. It’s very difficult to keep the qubits coherent. Suffice to say that for a universal quantum computer there are much, much fewer stable qubits for the state of the art for a universal quantum computer.

So quantum annealing is really trying to, as I said, harness the natural evolution of the quantum state. It’s not trying to wrangle the quantum states quite as much or at all. And this is a special case of universal quantum computing that could be referred to as adiabatic quantum computing.

I think those terms adiabatic quantum computing and quantum annealing can kind of be used together. D-Wave is at the forefront of building computing systems that use adiabatic methods. I actually come from the climatology world from way, way back, where an adiabatic lapse rate, for example, refers to the changes in the atmosphere as you go higher and higher in altitude. So this goes back to what I said earlier: Quantum annealing is trying to find the minimum energy state of something. Just like in the atmosphere. That’s why we use that term adiabatic.

If you think about sending a bouncing ball down a slope, when does it reach its final state? That essentially is the simple analogy. You’re trying to find the minimum energy state of any given system. That’s what quantum annealing is really good at trying to solve.

TCTim CallanSo quantum annealing as a process, how does it connect to breaking cryptography?

Jason SorokoWe’re going to get to that just a second. I attended DEF CON and Black Hat just recently in Las Vegas, and Andreas Baumhof out of Quintessence gave a great talk at DEF CON specifically about quantum annealing. He referred to some research that recently came out that provided a fairly massive breakthrough. This was out of 2018. It was Jiang et al., “Quantum Annealing for Prime Factorization.”

It was Purdue and Oakridge Labs that actually published this, basically trying to use quantum annealing methods to solve prime factorization, which obviously then lends quantum annealing as a methodology toolset to be able to then perhaps break current types of cryptography.

But let’s just go back one step. Currently we’re talking about Shor’s Algorithm most of the time. Most of the time when you’re talking about quantum resistance, what are you trying to be resistant against? You’re trying to be resistant against Shor’s Algorithm being used on a universal quantum computer. A gate-model quantum computer for example. An adiabatic quantum computer—quantum annealing—it’s not something you run Shor’s Algorithm on because of the fact that Shor’s Algorithm requires that complex set of state changes. That’s why you’d use a universal quantum computer for Shor’s Algorithm.

Therefore, since that’s not a direct algorithm that you can use on a quantum annealing computer, what is there? That’s where this new research that came out in 2018 and some additional advances in 2019 have come out, Tim, to answer your question. Now people are using quantum annealing computers to be able to solve prime factorization.

TCTim CallanSo is this a theoretical approach or is this a real approach that’s having results?

Jason SorokoThe takeaway here in terms of results is I'm not here to announce that RSA-2048 and Elliptic Curve have been solved, right?

TCTim CallanRight.

Jason SorokoThose have not been broken because we have not gotten to the number of stable qubits yet in either a universal quantum computer or quantum annealing. But I think one of the things to keep in mind is that quantum annealing because of the fact that it’s trying to harness the natural evolution of quantum states, it’s not as concerned about having a lot of difficultly keeping together qubits. In other words, the coherence of the qubit is not necessary to be in such a stringent state as for a universal quantum computer. The end resultis that the number of qubits that are currently being run in the state-of-the-art quantum annealing computers such as D-Wave computers is much higher.

So therefore, you then have to ask the question, “Are we further ahead to break RSA and ECC with a quantum annealing computer?”

TCTim CallanThere’s at least a chance that a quantum annealing computer is going to accelerate the progress, if that’s the word you want to use, toward having a quantum computer that basically renders RSA and ECC unusable. Is that a correct statement?

Jason SorokoI think that’s what Andreas Baumhof was trying to conclude within the talk at DEF CON. Which is, we’ve heard all about the Z date, out of the University of Waterloo. That is referring to universal quantum computers with respect directly to Shor’s Algorithm. What we have to do now is take a look at some of the other viable means of using a quantum computer and other algorithms that are now with us.

One of the other conclusions that I think Andreas Baumhof was making is let’s look at all the quick advances that have been made. So, in other words you get a couple university researchers who come up with a bright idea and then a few more researchers down the road go, “Hey, I can do that even better.” Then the ball starts rolling and the optimizations I think are—this is something that you and I talked about in a previous podcast about Eureka moments. We suspected there might be one or two. I think what’s interesting is that some of the Eureka moments are happening in some of these alternative methods such as quantum annealing.

TCTim CallanRight. And that’s one of the dangers I think of discussing the Z date is it seems unlikely that it is further away than you would predict if you look at a progress chart about quantum computers. But of course, we’re talking about exactly this: Someone comes and says, “Oh, I have an entirely different technique” or, “Oh, I have an entirely different technique for some component of this and it makes it all better” or “I have an entirely different technique and now all of a sudden I don’t need as many qubits as we thought,” right?

Jason SorokoRight.

TCTim CallanAnd as they do these things, those dates could theoretically move forward by big chunks all at once.

Jason SorokoYou asked the question, how real is this part of that 2018 paper? There was an algorithm that was successfully run on a D-Wave 2000Q quantum annealer. Therefore, we know these things are not just on chalkboards or in people’s heads. I think it’s at early stages, but there is software being run on these types of computers.

TCTim CallanA reminder for the listeners: You don’t even need this to be something that is mainstream, that I can just go out and buy at the local computer store and have on my desk. As long as this kind of computer can be built and used with some pretty heavy investment of resources, then you still could look at a scenario where a state or a very large criminal enterprise could be using them. And once we’re at that level, we’re at the level where basically we need to be worried. The fact that this is just running in university laboratories doesn’t mean it’s as far off as you might imagine.

Jason SorokoWhat I’d suggest to anybody listening right now is the DEF CON media server for DEF CON 27 is public right now. In fact, Tim, I think you downloaded this paper fairly recently to be able to have a look at it.

TCTim CallanCorrect.

Jason SorokoThere’s at least 70 plus slides in the deck. It’s a pretty heavy deck, but I would say that the conclusion slides are really worth looking at. Can I throw a couple of Andreas Baumhof’s conclusions out at you right now? Just for your reaction.

TCTim CallanPlease do.

Jason SorokoInteresting how he sets this up. He has myth and reality. So one of the myths he’s saying is that Shor’s Algorithm is currently the best known algorithm to factor integers. Well it probably is the best known. But he’s claiming that the reality is that quantum annealing-based algorithms are outperforming Shor’s Algorithm by a factor of a thousand.

TCTim CallanOh wow. That’s hugely important. Because we all hear about Shor’s Algorithm. We talk about Shor’s Algorithm and I guess in a classic—I don’t know, can you say classic quantum computing? Is that fair?

But in a pure quantum computing environment it is the best approach. Quantum annealing counts as a Eureka moment, right? If quantum annealing can be fundamentally better by three orders of magnitude, that’s hugely important.

Jason SorokoI think, Tim, the terminology, we’re going to have get used to using is universal quantum computing.

TCTim CallanGotcha.

Jason SorokoOr perhaps of which adiabatic quantum computing is part of it but gate-based, it typically is what we’re referring to when we’re talking about Shor’s Algorithm.

Although other, other forms of quantum computing can also run Shor’s as well. So it gets complicated, but I think universal quantum computer versus a quantum annealing computer is the terminology we should be using.

TCTim CallanAlright. So give me another myth.

Jason Soroko“Shor’s Algorithm will eventually break cryptography.” I mean isn’t that something we’ve been talking about for a while now.

TCTim CallanYes, of course it will. Everybody knows that.

Jason SorokoSure. Reality: Shor’s Algorithm was never meant to be implemented; derivations of it will be used to break cryptography.

TCTim CallanOk. So that’s a fair, that’s a fair comment. It’s a subtlety, but the point being that it was work that was done as a result of Shor’s Algorithm, this is really going to break cryptography. But it was work that was done as a result of Shor’s Algorithm that got us to where we are with quantum computers in the first place.

Jason SorokoAbsolutely. So another one of these, remember we talked about the Z date. “Quantum computing may be twenty years away and not ten years.” In other words, there might be some people out there saying the Z date might be just too aggressive. The reality in this conclusion is, it all depends on the breakthroughs in the number of stated qubit, the quality of the qubits, the quality of gate operation, and the optimizations and algorithms.

I think the conclusion the author here is trying to make is, if you take a look at the breakthroughs over the past, all those four areas in the past six years, it probably would be bad to assume that the breakthroughs are going to either slow down or not happen at all from now on.

TCTim CallanHugely important. Let’s remember, 1/0 gate-based computing has a legacy that goes back to the 1950’s, so it’s very stable compared to quantum computing. And that means it’s better understood. Likewise RSA has a legacy that goes back to the 1980’s. Once again, therefore it’s very stable, very tested. A lot of people have poked at it a lot of different ways.

One of things that it’s important about quantum computing and about the quantum resistant cryptographic techniques that we’re going to be looking at is they’re very new. They haven’t gone through the same level of vetting and testing and just real-world rigorous survival that these others have. As a consequence, there’s much more opportunity for unknowns.

Jason SorokoLet’s think now also about quantum annealing computers in other areas where they’re used. Because anywhere where there’s a big, commercial push on something, money will follow, right?

TCTim CallanRight.

Jason SorokoAnd why is D-Wave building these computers? They’re not building them for fun. They’re building them because of the fact that they solve major commercial problems. Any types of these optimization issues—of which prime factorization just happens to be one—now that we’ve seen the research, it’s tremendously powerful for things such as artificial intelligence and machine learning. All these things that have become buzz words.

Essentially, these are optimization problems, and they can mathematically be broken down to do so. So therefore, when you need an incredibly powerful quick determination of the best, most optimal solution for a given problem set or a current state of a world, a quantum annealing computer might be all you need. You might not need a universal quantum computer. I think that’s why D-Wave is in business and that’s why they’re trying to have bigger and bigger quantum annealing computers all the time.

It’s interesting, Tim, that the rapid pace of optimizations in quantum annealing computers is because of the fact that it’s not just cryptography, because the rest of the commercial world is very interested in solving these problems.

Tim: And when

TCTim CallanAnd when there’s commercialization, when there are economies of scale, when there are real world problems and money to be made, one of the things you see is that technology progress increases. Just because more people are working on it. More people are trying to solve it. There’s more innovation. Things like manufacturing and supply chain get better. And that ultimately means progress advances.

So the more uses that there are for a quantum annealing solution, the more we should expect quantum annealing hardware and software to make faster progress. I think that’s an important point.

The other important point connected to that of course is that you find that different knowledge gets applied different ways. So, as people are working on one aspect of quantum annealing, one of the consequences is some smart person is going to say, “Ah ha, I can apply that over here as well.” And that’s the other thing you see when a technology platform is used broadly and massively is that more of this kind of cross-pollenization of ideas occurs.

Jason SorokoThis podcast was about trying to raise the awareness of different algorithms, different ways of thinking, and those are getting better by the day as we speak. So, you know cryptographic agility, very important.

Stay informed with expert insights

Subscribe to Root Causes for engaging discussions on PKI, digital security, and best practices for protecting your organization's critical assets. Don’t miss an episode!