Ups and downs of post-quantum cryptography—and our hybrid solution

On April 10, 2024, a paper with the title Quantum Algorithms for Lattice Problems was published on the IACR (International Association for Cryptologic Research) preprint service. Despite the unassuming title, this paper made a bold claim that could have toppled the world’s attempts to create post-quantum safe encryption.

In this blog post, we look at the claim that was made, especially as it pertained to the choice of Kyber, and what happened next. We also delve into how our VPN’s post-quantum encryption could have been affected.

Kyber’s security called into question

Kyber is a lattice-based encryption algorithm designed to be secure against attacks by quantum computers. The National Institute of Standards and Technology (NIST) ran a competition to help determine which of many candidates would progress towards becoming an official standard and recommendation, and Kyber effectively won. 

However, in the paper in question, Dr. Yilei Chen, an assistant professor at Tsinghua University, claimed to have found a quantum algorithm that could solve the learning with errors problem (LWE)—which in turn meant it had found a way to break (or significantly weaken) Kyber.

This was headline news in some circles: If the claim held, it would mean that the technology on which the world has based the latest post-quantum tech is fundamentally broken. 

At this stage, a lot of time, energy, and money has gone into standardizing on Kyber with all modern browsers supporting it. It is also Kyber that we use for ExpressVPN’s post-quantum protections (via our protocol Lightway). If significant flaws were found at this stage, it would mean starting again from scratch, and undoing all the work that has already been done. Obviously this would not only be devastating in terms of the amount of time and work already invested, but it would further shake confidence in the solutions that have been created.

It was thus a major claim—but given the academic credentials of who was making the claim and the significant work that had gone into the discovery, it certainly looked like the claim could be valid.

All eyes on post-quantum cryptography

So how assured can we be in the strength of existing post-quantum cryptography? I am not a cryptographer, nor do I have a strong background in math, but the people who have worked for years on post-quantum technologies do. Those who created the Open Quantum Safe Project—which aims to support the transition to quantum-resistant cryptography—are literally leaders in their fields. They’ve not only checked the math, but they’ve implemented the technologies and verified it themselves. All of this was done in the open, and so it had a lot of eyes on the project, and a lot of people giving feedback. This would make it much more difficult for a serious error to slip through.

But that doesn’t mean that that can’t happen. It’s also not uncommon for engineers to not see the wood for the trees until it’s pointed out to them by someone outside of the system. After all, this is how such advancements are made—by people plugging and chipping away at these sorts of challenging problems.

Carl Sagan once said, “Extraordinary claims require extraordinary evidence.” In general this is good advice—if something is claimed to change the status quo, it is reasonable to hold the evidence required to a suitably robust standard. And that is what happened in the case of the paper put forth.

Kyber security remains unbroken

On April 18, Dr. Chen updated the paper to acknowledge that a bug had been identified (independently by Hongxun Wu and Thomas Vidick) in the algorithm he created, and that the paper’s claim indeed did not hold. He has left the paper available so that others may still build upon it.

It is important to note that Dr. Chen is a legitimate researcher and works at one of the top research universities in China. The process he followed with his paper is consistent with best practices for the field. By submitting a preprint, he was able to solicit fast feedback from the cryptographic community with the intention of improving the paper. If the feedback had shown everything looking solid, he would likely have submitted the paper to a peer-reviewed journal.

In this case, however, he received critical feedback on the algorithm that called into doubt whether the algorithm used would work as intended. The best thing he could have done at that stage (once he had verified those counterclaims) was to gracefully accept the feedback, withdraw his own claim, and get back to work. By all accounts, that is exactly what he did, and this shows strong academic integrity and a commitment to progressing the field.

ExpressVPN’s hybrid encryption for post-quantum protection

At ExpressVPN, we always assumed that Kyber could be broken. After all, one of the contenders for selection (called Rainbow) ended up being broken on a single laptop. Not only was it not quantum safe, but it also wasn’t classically safe either.

That’s where hybrid encryption comes in. When deploying post-quantum protections on our Lightway protocol, we combined both the current classical state-of-the-art encryption technology and Kyber to produce a key that would require an attacker to break both forms of key exchange. 

By doing this, if Kyber turns out to be susceptible to attack, then you still have the security of classical P521 protecting you. And in the future if it turns out that quantum computers can break P521, well, you also have Kyber, which as of today is the best-known way to protect you against that threat. In other words, you get a two-layered shield of sorts when using Lightway. 

For the majority of the cryptographic community, the retraction of the claim means that we can breathe a little easier. It is likely that we will see more claims on breaking lattice encryption, and eventually maybe one of them will be successful. This is just part of the rigor that we must place on our encryption technologies to ensure we are as safe as possible.

ExpressVPN will continue to use hybrid cryptography to offer the best of both worlds when it comes to protecting our users. We have no plans to switch to Kyber only and imagine that hybrid encryption will be with us for many years to come.