# 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.