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.