On April 10, 2024, a Shanghai researcher, Yilei Chen, purportedly solved the hard problem underlying quantum algorithms using a Learning With Errors (LWE) approach.
We’ll go into detail about what LWE is in just a bit. But for now, let’s talk about this recent cryptographic development. This vulnerability opened cryptographers’ eyes, because two of NIST’s standardized post-quantum algorithms are based on lattices and use LWE: CRYSTALS-Kyber and CRYSTALS-Dilithium.
While Chen, and others, did not claim that the bug applied directly to the standardized algorithms, nor did they claim Chen’s work would totally break LWE, the research is nascent, and the community is still processing what the new development means for post-quantum cryptography (PQC).
April 18 Update: A buggy discovery
On April 18, another two researchers, Hongxun Wu and Thomas Vidick, discovered a bug in Step 9 of Chen’s 65-page paper, which Chen couldn’t fix.
So, while the paper is still an interesting development for technical researchers, it seems any potential quantum crypto crisis has been averted.
But, the development brings up two important points:
- Most of NIST’s standardized algorithms (so far) utilize a lattice-based approach, leaving us with few alternatives.
- Hybrid approaches to cryptography are still more secure. If one layer, quantum or traditional, is cracked, a threat actor still must find their way through the remaining layer.
Prepare for the Future of Cybersecurity: InfoSec's Guide to Post-Quantum Readiness
What is lattice-based cryptography?
Lattice-based cryptography is built on mathematical problems using lattices. To borrow an analogy from Utimaco, you can think of a lattice like the grid on a piece of graph paper—and that grid extends infinitely.
The lattice, also infinite, uses sets of points, known as vectors, and then adds and subtracts numbers in any integer multiples. The hard problem involved requires a cryptanalyst to find points close to 0 or another point.
To bring this back to a practical cryptography example, one set of points would be your private key, and another—likely much further away on the grid—would be your public key. And because brute force is the best way of finding those points, lattice-based algorithms are extremely secure, thought to be resistant to both classic and quantum computer attacks.
A bit more detail on lattice-based crypto: the hard problems
Without getting too technical, the hard problems underpinning lattice-based algorithms commonly include:
- Shortest Vector Problem (SVP): For any lattice, it’s hard to find the shortest vector. That complexity compounds in lattices with greater dimensions.
- Closest Vector Problem (CVP): Similar to SVP, instead of the shortest, it’s the closest vector to 0 or another basis.
- Learning with Errors (LWE): A way to hide a secret’s value by introducing noise. In other words, you can represent secret information as a set of mathematical equations with errors.
To learn more, you can head over here or here.
Why hybrid encryption is key
As you can see, lattice-based cryptography is thought to be very secure, but Chen’s research brings up one other critical point: hybrids between classical and quantum cryptography offer a more solid line of defense.
For example, if this vulnerability did actually turn out to impact a post-quantum algorithm like Kyber or Dilithium, and a piece of data was also encrypted with a traditional method, it would still be more secure than one or the other. To look at a realistic example, Apple recently implemented this approach for iMessages.
You can learn more about hybrid encryption in this related blog post on store now, decrypt later (SNDL) attacks, as well as how to take your first steps toward enhanced cybersecurity in the PQC era.
How Venafi helps you prepare for tomorrow’s post-quantum world, today
Though this vulnerability turned out to be a false alarm, Chen’s research underscores the need for a crypto-agile foundation, and an automated, centralized platform that allows bulk revocation and replacement of machine identities, should any researchers find weaknesses in otherwise secure algorithms.
Venafi’s quantum-readiness capabilities can ensure you’re ready, long before quantum computers arrive on the scene.
Through the Venafi Control Plane—the industry’s preferred platform for orchestrating machine identities—your team is equipped with the observability, automation and crypto-agility you need to rapidly migrate from vulnerable cryptography to quantum-resistant schemes.
- Observability: Discover and monitor all machine identities, their health and cryptographic status.
- Consistency: Define and enforce policies using automation and approval workflows.
- Reliability: Reduce downtime with a fast, automated service that scales.
- Flexibility: Choose the best post-quantum approach for your specific business requirements.
For more on post-quantum readiness, including pro tips on a successful migration, check out our eBook: InfoSec’s Guide to Post-Quantum Readiness.
Test and experiment with quantum solutions in your own environment
For years, Venafi has been empowering organizations to issue hybrid certificates, get easy access to quantum PKI and maintain robust security.
To learn more about our Ecosystem’s hybrid quantum integrations, check out our solutions page.
Or if you’d like to start testing and experimenting on your own, dive into our Crypto4A and ISARA sandboxes.
- To experiment with Crypto4A HSMs, head over here.
- To experiment with ISARA’s quantum-safe certificates, head over here.
Have any questions about how machine identity management plays a role in your post-quantum readiness? Reach out to the Venafi team. And don’t forget to register for Machine Identity Management Summit 2024, where you’ll discover how to fortify your infrastructure today for victory tomorrow.
Even against quantum threats.