Podcast | Is Post-Quantum Cryptography at Risk?

Konstantinos Karagiannis: After spending so much time prepping all of you for the migration of PQC, I and many others in my field face the possibility that we would have to come up with yet another call for math-based solutions to the quantum threat.

Is post-quantum cryptography safe from quantum computing? Do we need thousands of qubits to attack RSA? We examine some of the challenges to PQC strength and timeline that have recently emerged in the world of scientific papers and consider what makes peer review such a crucial part of the process. Find out if we’re all more doomed than we thought in this episode of The Post-Quantum World. I’m your host, Konstantinos Karagiannis. I lead Quantum Computing Services at Protiviti, where we’re helping companies prepare for the benefits and threats of this exploding field. I hope you’ll join each episode as we explore the technology and business impacts of this post-quantum era.

This episode is brought to you by science and the peer-review process. OK — it’s not a real sponsorship, as we don’t accept those here, but you’ll see that peer review is very much a theme of this episode.

Over the past year or so, researchers have literally or figuratively attacked post-quantum cryptography and the timeline for its implementation. I’ve touched on some of these instances in this podcast, as well as in blogs, YouTube videos and interviews. Don’t worry — I’ll hit the highlights of the older attacks later on, rather than send you down a link wormhole. First, we’ll focus on the latest work that made it seem like PQC is doomed.

On April 10, 2024, Yilei Chen from Tsinghua University in Shanghai submitted a paper for peer review. Called Quantum Algorithms for Lattice Problems, this paper was a seismic event in the cryptographic community. I live in New York City, and I felt the shockwaves of the paper more than I felt the 4.6 earthquake we had five days before.

If you’re a listener, you’ve likely heard of Shor’s algorithm, which can factor large numbers into primes and threaten RSA by uncovering secret keys in use. Chen claimed that he found something similar for lattice-based cryptography, which is considered quantum-safe. Chen’s quantum algorithm claimed to solve the learning-with-errors, or LWE, problem, yielding secret information. Did Chen find a new Shor’s algorithm of sorts? Could this be developed into a full exploit against the coming NIST ciphers? For instance, the first finalist, CRYSTALS-Kyber, is built upon module LWE.

I’ll leave you in suspense for a moment to make an important point: One of the things that makes scientific research so great, be it quantum physics, quantum computing, cryptography or even geology, is that work gets described in papers that are then peer-reviewed. Contrary to conspiracy theories, you can’t buy off researchers. You could Google instances where such actions are alleged, but I’m saying you can’t truly succeed in such subterfuge.

That’s just an extreme example. Most incorrect information that gets put out for peer review is because of an honest error — by far. That’s the beauty of peer review: Others will catch it. Ultimately, whatever you publish will be scrutinised by others in your field. When you publish a paper to be pored over by other experts, you’re trying to make a name for yourself by having others validate your work, reproduce it and maybe praise it.

Conversely, some colleagues and peers try to make a name for themselves by proving you wrong. It’s not malicious (at least, not usually). It’s all for the good of science. Remember what happened with LK-99 when the world thought we might have room-temperature superconductivity? The scientific world tried to reproduce the results but couldn’t. Science won in the end.

Chen’s paper set off something similar in the world of cryptography, although with a little less media frenzy. Even though Chen wasn’t claiming a ready-to-use exploit against a NIST PQC finalist, the threat of this happening down the line was there. I was a bit anxious. After spending so much time prepping all of you for the migration to PQC, I, and many others in my field, faced the possibility that we would have to come up with yet another call for math-based solutions to the quantum threat. Starting from scratch all over again? Yikes! We’re already running out of time, what with logical qubits starting to appear this year. What to do? I’m glad I shave my head daily, or I would have pulled my hair out.

Seriously, though, it was a potential crisis. Luckily, we only had to endure agita for about a week. On April 18, the paper was retracted. What happened? You might have guessed —peer review.

The approach Chen proposed was a polynomial-time quantum algorithm for solving LWE. As I mentioned, LWE is a vital part of lattice-based cryptography. I promise no math will follow. I’m going to try to illustrate some complex topics verbally. My apologies to my colleagues if I oversimplify with my examples, but I want to keep this accessible to all.

Think of lattices as an infinite field of points, like a grid of dots. You might have seen something like this printed on a specialty writing pad or journal. With mathematical lattices, you can solve complex problems, like the shortest-vector problem, or SVP.

You might recall that a vector is drawn as an arrow of a specific length because it has both magnitude and direction. To explain SVP simply, we’ll say the goal is to find the shortest distance from one point to another in a lattice, or field of dots — that is, the shortest arrow pointing from one specific dot to another. Doesn’t sound that difficult? Oh, I forgot to mention that it’s not a two-dimensional field, like on paper. And it’s not a three-dimensional field, like marbles floating in a box. This field of dots can have thousands of dimensions. Yeah, thousands.

Remember in Interstellar, Matthew McConaughy’s character entered a tesseract in the black hole? Did that make your head hurt? That’s just a cube with one extra dimension. Now, imagine Christopher Nolan trying to show thousands of dimensions. It’s hard to conceive what this would look like, but for our discussion, try to imagine solving the shortest-vector problem in such a construct.

Because of these many dimensions, a solution vector can be an arrow of seemingly any potential length going in infinite directions.

Now, what is LWE? Learning with errors is an approach where a secret vector is multiplied by numerous other vectors. It sounds difficult enough to find the secret lattice vector after doing that, right? We’re already talking about doing dot operations on multidimensional arrows in directions we can’t visualise. Seems like an almost infinite space of possibilities. But to make things harder, LWE adds noise or errors to the calculation. Without getting into the math here, you should see why we’re discussing an operation that should be wildly difficult to reverse to find the secret vector or key.

Chen, in his paper, claimed to have found an approach that solves LWE with certain polynomial module-noise ratios. It’s a long, technical paper, but he goes through multiple pages of steps to describe how his quantum algorithm works. Again, it didn’t claim to attack a current NIST finalist, but the fear was that it could lead to such attacks in the future.

As part of the peer-review process, two researchers, Hongxun Wu and Thomas Vidick, independently discovered the same bug in the algorithm on step nine. The updated paper in the show notes highlights this error on page 37. Chen admitted he didn’t know how to fix the error and left his paper up in case any of his work might help future LWE researchers.

Crisis averted — unless one of those future researchers knows how to fix the bug? I hope not.

In this case, two independent researchers found a bug and informed Chen. In other cases, entire papers are written to disprove a team’s work.

You might recall another paper from China that caused quite an uproar — this one in December 2022. Called Factoring Integers With Sublinear Resources on a Superconducting Quantum Processor, the paper claimed that using a quantum approximation optimisation algorithm (QAOA) could allow for cracking RSA with only 372 physical qubits. We have more qubits than that already, so this was quite a disaster facing the infosec community. We had thought we had until 2030 or later, at least.

The paper used a hybrid classical and quantum approach. It is based on much earlier work by Claus Peter Schnorr (not to be confused with Peter Shor of Shor’s algorithm fame). Schnorr released a factoring algorithm back in 1991 that uses a lattice approach called the closest-vector problem, or CVP. (This is similar to SVP, which I discussed above.) While the Chinese team used this old approach, Schnorr also released something controversial in 2021 that used SVP. I want to bring that up here to avoid confusion. The 1991 CVP approach was used in the Chinese paper, not the 2021 SVP approach. I link the 2021 paper in the show notes if you want to take a look. It was, not surprisingly, called Fast Factoring Integers by SVP Algorithms. Schnorr’s SVP work remains controversial for some of its speed claims.

Now, back to the Chinese paper. Researchers built off the classical CVP work and added QAOA. The flow was basically this: classical preprocessing of the problem with CVP and a lattice-reduction algorithm, followed by quantum optimisation, and then a feeding of the results back to Schnorr’s factoring algorithm. You then get the factors — the answer.

It sounded devastating — sort of. While the team used 10 superconducting qubits to factor a 48-bit number, they extrapolated that 372 qubits would handle 2048-bit RSA. Skeptics were not convinced that QAOA had ever shown a large speedup of its own, and most researchers were only mildly uneasy.

One team from Google Research went deeper in its peer review of the Chinese paper and created a paper called A Comment on ‘Factoring Integers With Sublinear Resources on a Superconducting Quantum Processor.’ The title is apt, as this “comment” is only six pages long, including sources and appendices. In short, this short paper shows that the Chinese team's claims don’t scale: It wasn’t possible to factor numbers larger than 70 bits with the hybrid approach. The team put all code and data on GitHub to encourage even further peer review.

Another alleged attack on PQC came in the form of a side-channel attack on CRYSTALS-Kyber in October 2022. That’s just a few months after CRYSTALS-Kyber was named a NIST finalist. Side-channel attacks have been around for a while and allow you to obtain information from a system in a different channel than expected. For example, rather than accessing the output of a CPU, you analyse the chip’s power consumption to try and figure out what the CPU is doing. In the paper A Side-Channel Attack on a Hardware Implementation of CRYSTALS-Kyber, the team from the KTH Royal Institute describes how they hacked the NIST finalist. There’s just one problem: They weren’t actually hacking CRYSTALS-Kyber.

A future version of CRYSTALS-Kyber will need to use something called masking to go into production. This approach is somewhat ironically designed to protect against side-channel attacks. Basically, masking splits a secret into several pieces, and an attacker must gather them all to try and rebuild the secret. The more masks or pieces, the harder it is to put them back together.

The CRYSTALS-Kyber candidate code did not contain high-order masking of this type, so the KTH researchers wrote their own implementation and then attacked it. They used an AI to analyse the data collected from power-trace leakage detection and successfully recreated the secret 99% of the time. While we learned a lot about how to not implement masking from this paper, I have to reiterate that they were not hacking a production version of CRYSTALS-Kyber.

That finalist still stands, and as we saw, so do concepts like lattice-based PQC and the timelines associated with cracking RSA in the future.

Everything we’ve discussed on this podcast still applies. The time to begin inventorying your cryptography is now. The time to begin becoming crypto-agile is now. The time to begin the journey to implementing PQC may be only months away, if you’re listening to this as it’s released. The NIST ciphers are expected this year.

And if something changes, I’ll be sure to tell you what the peer-reviewed verdict is.

That does it for this episode. Thanks to all the researchers who participate in peer reviews and keep science moving forward.

And thank you for listening. If you enjoyed the show, please subscribe to Protiviti’s The Post-Quantum World and maybe leave a review to help others find us.

Be sure to follow me on all socials at Konstant Hacker— that’s Konstant with a K...Hacker. You’ll find links there to what we’re doing in Quantum Computing Services at Protiviti. You can also DM me questions or suggestions for what you’d like to hear on the show.

For more information on our Quantum Services, check out Protiviti.com or follow ProtivitiTech on Twitter and LinkedIn.

Until next time, be kind, and stay quantum curious.