Did China break encryption? Protiviti’s quantum director sets the record straight

Did China break encryption? Protiviti’s quantum director sets the record straight

Joe Kornik: Welcome to the VISION by Protiviti Interview. I’m Joe Kornik, Editor-in-Chief of VISION by Protiviti, our global content resource examining big themes that will impact the C-suite and executive board rooms worldwide. Today, we’re exploring the future of privacy, and I’m joined by my Protiviti colleague, Konstantinos Karagiannis, Director of Quantum Computing Services.

Konstantinos has been helping organizations get ready for quantum opportunities and threats that lie ahead. He’s been involved in the quantum computing industry since 2012, and is the host of Protiviti’s popular podcast, “The Post-Quantum World.” Konstantinos, thank you so much for joining me today.

Konstantinos Karagiannis: Yes, thanks for having me. It’s always great to join you.

Kornik: So, Konstantinos, I’ve been hearing more and more about quantum. I know you’ve been at this for a long time but lately, I’ve been hearing more and more about it in the media, including in mid-October, something happened in China. I’m not going to pretend to understand exactly what happened, but I’ve heard things or seen things about potentially military-grade encryption being cracked, which seems way earlier than we thought, I think. So, is the end of encryption here early, it’s what I know some in the media have called “Q-Day.” Has that arrived?

Karagiannis: The short answer is no, which is good. It’s not the end of encryption already. It’s funny that this Chinese story broke pretty heavily over the weekend as we’re recording this, and I was like, “I’m going to have an interesting week. I already know this is going to be one where I’m going to be asked a lot of interesting things.

So, basically, we don’t have a great translation of this Chinese paper. A Chinese paper was published, and in it they make some pretty strong claims, but the abstract is in English and then after that it dives right into Chinese. So, if you try and translate it with machines or whatever, AI, you end up with some holes, and as a result, no one’s reproduced this yet. So, I can’t come on today and say that based on reproductions and other teams that I could say that this paper is even real, but let’s say the claims are true. Let’s pretend it’s not some nation-state psy-op to try and freak out the West of something. Even if the claims are 100% true, it doesn’t really spell the end of encryption. So, that’s the awesome news, right? Even worst case, it’s not all over.

People might have been hearing for a while now that we need fault-tolerant quantum computing to crack encryption, and that just means that quantum computers are noisy. They’re prone to interference, the qubits fall apart, you can’t do the complicated math of Shor’s algorithm to crack something like RSA. So, we need error correction. These things are starting to be built, error-correcting machines, but it could be 10 years or longer before we have one powerful enough using those traditional paradigms to crack encryption.

What’s scary about this Chinese paper is that they used the current annealing quantum computer from D-Wave. That’s a machine that’s on the cloud right now that you can access and use today. It raises all sorts of questions about access, where did these researchers come in from, D-Wave’s technically Canadian. So, it’s all this stuff, because your listeners might have heard of the quantum export bans going on. So, I can’t comment on that, I don’t know how they got access to it, but basically this machine exists and can be used.

So, annealing is different. It’s not error corrected. It’s not even designed to give you the correct answer. A gate-based quantum computer, the ones that we thought would be cracking encryption, they’re designed to take a problem through a series of quantum gates and give you a definitive this or that, you know, whatever your problem is. Annealing is more like an optimization finder. It’s sort of like a global optimization peaks-and-valleys solver.

So, if I were to ask you to imagine, I love this example, driving around the United States and finding the highest and lowest points, that would take you forever; whereas an annealer can literally do something called “tunneling”; it can move through all of those peaks and valleys and find the lowest one, let’s say. That kind of optimization machine is what they used in this problem. So, that’s a little scary because it’s a new approach.

Kornik: Right, and I was reading some of the media reports and the researchers, I guess, claim to have factored a 50-bit number. Can you explain the significance of that in the context of RSA encryption?

Karagiannis: Sure. So, a 50-bit number, first of all, is not terribly large, in fact we’ve tangoed in this area before and I’ll talk about that a little bit later, but basically, they picked a number, let’s say 2289753, and they wanted to try and get its factors. A 50-bit number, you can think of it as 50 bits, you know, a bit is a zero or one, right? So, if you were to string 50 of them in a row, each of those bits has two options, a zero or a one. Because of that, the math gets very interesting. It becomes 2ⁿ, so it would be 2 to the 50th power. Those are all the possible combinations of ones and zeros.

That’s a pretty big number, right? But if you’re going to try and crack something like RSA, you’re talking about a 2048-bit key. That is way bigger. You’re thinking more along the lines of 2 to the 2048th power. These numbers get insanely large. The universe only has 2 to the 80th power particles in it. So, these are just numbers that you can’t even fathom. So, it’s not like 2 to the 50 is anywhere near or even touching 2048; exponential math is not really something humans are comfortable thinking about. Like you could represent that number I cited before, that seven digits, right? If you were to represent a 2048-bit number, you would use 617 digits. So, take that number they factored, add 610 more digits to it, and that’s just one. That’s crazy. That’s not even scratching the surface.

So, as a result, we’re nowhere near anything that could be called military-grade encryption or a real risk today. That’s kind of like for starters.

Kornik: Okay. Well, that certainly makes me feel better and I’m guessing most of the people watching also feel better. What are some of the practical challenges in scaling quantum annealing to a level where it could truly threaten our encryption standards?

Karagiannis: We’re having a hard time scaling regular gate-based machines, right? That’s why we don’t have these fault-tolerant systems yet. When it comes to annealing, the question is, does this paper show any kind of linear path that scaling even becomes an issue? In the paper, they push for a hybrid quantum classical approach. What that means is they’re using the optimization of the annealer to sort of bundle numbers in a way that you can optimally then apply classical approaches too.

So, you could think of it as, like, a search for the keys. You are kind of bundling likely places to look for the keys, and then you’re going to use classical hardware to look for the keys. That’s really hopelessly simplifying it. I just want to make sure that it doesn’t fly right over our listeners’ heads. So, that’s what’s happening. It’s kind of like a machine learning. They almost call it like an approach to machine learning, which it’s really not but they’re calling it that. This is like optimization.

So, because of that layout, they’re hoping that this will scale. That’s fair to hope that, but when you look at the classical systems that are involved, I’m not convinced that you can go much farther. Like even if you can optimize for a larger key search, I don’t think the hardware you then have to rely on to do the actual searching would be able to keep up. I think we’re going to hit the scale limit fast.

This isn’t the first time we’ve seen this kind of limitation. People might remember in December 2022, there was a paper that kind of created a stir, once again from China. It was called “Factoring integers with sublinear resources on a superconducting quantum processor.” It’s a big, crazy title, but basically in it, everyone might remember that they claimed to factor a 48-bit number with 10 of those gate-type qubits we talked about that we were building. Using extrapolation, they said you’d only need 372 to crack RSA. That’s terrifying because we thought we would need many, many thousands of error-corrected qubits to factor RSA. So, that was sort of a “sky is falling” situation.

Google researchers did a little bit of validation. Remember I said we don’t have access to the paper translated here so no one’s been able to reproduce the results, but Google researchers were able to work on the problem and prove that it would stop around 70-bits. So, the sky didn’t fall then, and right now, it might not be falling here either, because I have a feeling that if you try to scale this up, you’re going to have those classical system constrains that will kick in and sort of like protect it from getting too much farther.

That said, it’s interesting, and whenever we have new approaches like this, it makes me worry that some little kernel of them will show us a path forward. Some optimization process—there’ve been other papers too, I’m not going to go down rabbit holes—but everyone’s probably going to find something that fails but it still makes us go, “Okay, we might have something to worry about in the future where we can learn from this. So, there’s always that.

Kornik: Well, great. Thank you so much for shedding some light on that and making us feel perhaps a little bit better, or perhaps a little bit more on alert or high-alert as we probably all should be anyway.

We are sitting here in the middle of cybersecurity month, and VISION by Protiviti is focused on the future of privacy. So, I’m just curious, if we could take sort of a 30,000-foot view and talk a little bit about how organizations should be preparing for the potential impact of quantum computing on their cybersecurity infrastructure, on their data security framework, even if it’s maybe not the most immediate threat but we know it’s coming eventually.

Karagiannis: Sure. One big thing to point out is this approach that was published in the Chinese paper can’t touch the new NIST post-quantum cryptographic standards that were released on August 13th, 2024. The lattice-based approach in there is safe from this type of attack and safe from Shor’s algorithm, which is the quantum attack we were all worrying about.

So, really the best thing you could be doing right now is starting the migration plans for PQC. It’s time to start taking inventory, start looking at what cryptography you have in place, start looking at which critical assets you might want to protect first. Because migrating to new cryptography takes time and it’s tricky. So, that’s the journey you have to begin on. This paper will not, as I said, threaten PQC, so why not start looking towards PQC because that is going to be a path that everyone has to take.

It’s also important to note that eventually, NIST is going to start recommending the deprecation of some classical cyphers. So, whether you believe that quantum computers are 10 years or 10 million years away that can crack encryption, it doesn’t matter. Eventually, you’re going to start failing audits and things like that if you don’t have the latest cyphers in place. So, it is really time to start examining your environment and making a move to PQC.

Kornik: Well, Konstantinos, thank you so much for giving us that insight. We’re certainly glad that we’ve got you to sort it all out for us and to help us make sense of it. Even if I didn’t understand everything you said, I understood a great deal of it, so I am further along than I was before we started talking. So, thank you for that.

Karagiannis: Yes, and if I manage to recreate the paper, I’ll be sure to come on and tell you what happened.

Kornik: Yes, please do.

Karagiannis: Okay.

Kornik: Thanks, Konstantinos, I appreciate it, and thank you for watching the VISION by Protiviti interview. On behalf of Konstantinos Karagiannis, I’m Joe Kornik. We’ll see you next time.