A quick post on Chen’s algorithm
🌈 Abstract
The article discusses a new preprint by Yilei Chen that claims to have found a quantum algorithm that can efficiently solve certain lattice problems, which could potentially break some post-quantum cryptography schemes based on lattice problems.
🙋 Q&A
[01] Background on Cryptography and Quantum Threats
1. What are the "hard" mathematical problems that cryptographers use to build modern public-key encryption schemes?
- The main problems used are: factoring (RSA), discrete logarithm (Diffie-Hellman, DSA), and elliptic curve discrete logarithm (EC-Diffie-Hellman, ECDSA).
2. What is the threat posed by quantum computers to these "hard" problems?
- Researchers have devised algorithms that can solve these problems efficiently (in polynomial time) on a powerful enough quantum computer, which has not yet been built.
3. How has the threat of future quantum attacks inspired the cryptography community to respond?
- Industry, government, and academia have joined forces to develop "post-quantum" cryptographic schemes based on different mathematical problems that are believed to be resistant to quantum attacks.
- This includes NIST's Post-Quantum Cryptography (PQC) competition to standardize new quantum-resistant schemes.
4. What are the most popular class of post-quantum schemes, and what mathematical problems do they rely on?
- The most popular post-quantum schemes are based on problems related to mathematical objects called lattices, such as the Shortest Independent Vector Problem (SIVP) and the Guaranteed Approximate Shortest Vector Problem (GapSVP).
- Examples of NIST-approved lattice-based schemes include Kyber and Dilithium.
[02] Implications of Chen's Quantum Algorithm
1. What does Chen's preprint claim to have achieved?
- Chen's preprint claims to have found a new quantum algorithm that can efficiently solve the SIVP and GapSVP lattice problems for certain parameters.
2. What are the potential implications if Chen's result is correct?
- If the result holds up, it could allow future quantum computers to break some lattice-based post-quantum cryptography schemes that rely on the hardness of these specific lattice problems.
- However, the vulnerable parameters are very specific, and the algorithm's concrete complexity is not yet clear, so it may not immediately apply to the recently-standardized NIST lattice-based schemes like Kyber and Dilithium.
3. How do the author and others view the potential impact of this result?
- The author describes it as both a "great technical result" and a "mild disaster" for the cryptography community.
- Experts are still evaluating the correctness of the algorithm, as significant results have fallen apart upon closer inspection in the past.
- The implications will depend on the concrete details of the algorithm's running time and whether it can be improved upon.