Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

This paper presents a polynomial-time quantum attack that breaks standardized ML-KEM, Falcon, Hawk, and NTRU schemes over 2-power cyclotomic rings by utilizing a tower decomposition of the Principal Ideal Problem to achieve a high success probability with a verified approximation factor.

The Gist

The Big Picture: A Quantum Lockpick for Digital Vaults

Imagine that the world's most secure digital vaults (like those protecting government secrets or banking data) are built using a specific type of mathematical "maze." These mazes are based on complex shapes called lattices. Currently, we believe these mazes are too big and twisted for even the fastest supercomputers to solve, which is why they are considered safe for the future (Post-Quantum Cryptography).

This paper claims to have found a quantum master key that can unlock these specific mazes much faster than anyone thought possible. The authors, led by Ming-Xing Luo, argue that a quantum computer doesn't just need to be "fast"; it needs to be "smart" about the specific shape of the maze. By exploiting a hidden geometric shortcut, they can break the encryption schemes that NIST (the US standards body) recently selected as the new global standard.

The Four-Part Journey to the Solution

The paper is the final part of a four-part series. Think of it like a team of four detectives solving a massive heist, where each detective solved a different piece of the puzzle:

1. Part I (The Map): They proved that the "terrain" of these mazes is actually very simple. It's like discovering that a seemingly complex forest is actually a grid where every path leads to a single, central clearing. This means there are no dead ends or hidden loops that would confuse the attacker.
2. Part II (The Translation): They showed that you can translate the complex "Module" problem (a 3D maze) into a simpler "Ideal" problem (a 2D maze) without losing much information. It's like realizing a 3D puzzle is just a flat drawing folded up; you can unfold it easily.
3. Part III (The Ruler): They measured the "noise" in the system. In these mazes, there is always a little bit of static or fuzziness. They proved that this fuzziness is so small and predictable that it doesn't hide the solution. It's like realizing the fog in the forest is so thin you can see the exit sign clearly.
4. Part IV (The Attack - This Paper): This is the execution. They combined the map, the translation, and the ruler into a single, step-by-step recipe (an algorithm) that a quantum computer can follow to break the code.

How the Attack Works: The "Tower" Analogy

The core of their attack is a method called the Cyclotomic Tower.

Imagine you are trying to climb a massive, 256-story tower to reach the top floor where the secret is kept.

• The Old Way (Classical Computers): You try to climb every single step one by one. It would take forever (exponential time).
• The Quantum Way (The Authors' Method): They realized the tower is built in layers. Instead of climbing step-by-step, you can take an elevator that jumps from one floor to the next, solving a tiny puzzle at each stop.
  • Step 1: Go to the 3rd floor. Solve a tiny puzzle.
  • Step 2: Go to the 4th floor. Use the answer from the 3rd floor to solve a slightly bigger puzzle.
  • Step 3: Repeat this all the way to the top.

Because the tower is built in a specific mathematical pattern (powers of 2), this "elevator" method is incredibly efficient. The authors prove that a quantum computer can do this entire climb in polynomial time. In plain English: if the tower has 256 floors, a classical computer might take longer than the age of the universe, but a quantum computer could do it in the time it takes to brew a cup of coffee.

The Result: Breaking the Standards

The paper tests this method against the specific encryption standards NIST chose:

• ML-KEM (Kyber): The primary standard for secure key exchange.
• Falcon & Hawk: Standards for digital signatures (like a digital ID card).
• NTRU: Another family of encryption schemes.

The Findings:
The authors ran simulations and mathematical proofs showing that their quantum algorithm can break these codes with a 99% success rate.

• They calculated a "security margin." Imagine the lock requires a key that is 1,665 units long to break. Their quantum key is only about 103 units long.
• Because their key is so much shorter than the required length, the lock falls open easily.

They claim that all standardized parameter sets for these schemes are now considered "broken" if a large-scale quantum computer exists.

The Cost: How Big is the Quantum Computer?

You might wonder, "How powerful does this quantum computer need to be?"
The authors did the math on the resources required:

• Qubits (Quantum bits): They estimate you need about 1.4 million physical qubits (which translates to roughly 1,400 "logical" or error-corrected qubits).
• Time: The calculation would take a reasonable amount of time, roughly equivalent to the number of operations a modern supercomputer does in a few days, but performed by a quantum machine.

The Catch:
This is a theoretical breakthrough. We do not currently have quantum computers with 1.4 million qubits. However, the paper proves that if we build one, these specific encryption standards will not be safe.

Summary in One Sentence

This paper proves that a specific type of mathematical "maze" used in modern secure encryption has a hidden shortcut that a future quantum computer can exploit, allowing it to unlock the system with a key that is far smaller and easier to find than previously believed.

Technical Summary

Technical Summary: Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Problem Statement
The paper addresses the security of Module Learning With Errors (Module-LWE) based cryptographic schemes, specifically focusing on the NIST-standardized ML-KEM (formerly CRYSTALS-Kyber) and related lattice-based schemes (Falcon, Hawk, NTRU) constructed over 2-power cyclotomic rings ($R = \mathbb{Z}[\zeta_{2^k}]$). The central problem is the recovery of secret keys via the Shortest Vector Problem (SVP) on module lattices. While classical attacks rely on lattice reduction algorithms (e.g., BKZ) with exponential complexity, the paper investigates whether a quantum adversary can exploit the algebraic structure of cyclotomic rings to solve the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP) efficiently.

The authors identify two critical unresolved questions in prior work (specifically the CDPR attack):

1. Is the approximation factor achieved by the CDPR attack sufficiently small to break full ML-KEM secret keys (i.e., is $\gamma < q/2$)?
2. Does the underlying quantum PIP subroutine achieve true polynomial-time complexity without hidden exponential overheads or reliance on the Generalized Riemann Hypothesis (GRH)?

Methodology
The paper presents a unified, four-phase attack pipeline (Algorithm 1) that integrates results from Parts I–III of the series with a new polynomial-time quantum algorithm for PIP (Part IV).

1. Module-to-Ideal Reduction: The attack begins by reducing the Module-LWE instance to a Principal Ideal Problem. Using a Gram-Schmidt decomposition, the module basis is transformed into a product of principal ideals. The authors prove that the reduction introduces only a constant factor $\alpha_d = O(1)$, independent of the module rank $d$.
2. Quantum Tower PIP: Instead of solving the PIP in the full field $\mathbb{Q}(\zeta_{2^k})$ directly, the authors propose a "tower decomposition" strategy. They decompose the field into a chain of quadratic extensions: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • At each level $L$, the algorithm solves the PIP for the relative extension using the Abelian Hidden Subgroup Problem (HSP).
   • Crucially, the number of new unit generators at each level grows linearly ($\Delta r_L = 2^{L-3}$), keeping the HSP instance size polynomial.
   • This approach avoids the coefficient explosion inherent in standard power-basis representations and eliminates the need for GRH, as the class number of the maximal real subfield is proven to be 1 for $k \le 12$.
3. Log-Unit CVP: Once a generator $g$ of the ideal is found (which may be exponentially long), the algorithm computes its log-embedding. It then solves the Closest Vector Problem (CVP) on the log-unit lattice to find the unit discrepancy $\epsilon$ such that $g = g_0 \epsilon$, where $g_0$ is the short generator.
   • The authors utilize Babai's nearest-plane algorithm. They prove that for short ring generators, the target vector lies within the "capture radius" of the lattice, allowing Babai's algorithm to recover the unit discrepancy exactly.
4. Short Generator Recovery: The unit $\epsilon$ is reconstructed from the CVP solution, and the short generator is recovered as $g_0 = g \cdot \epsilon^{-1}$.

Key Contributions

• Polynomial-Time Quantum PIP: The paper provides the first construction of a polynomial-time quantum algorithm for the PIP over 2-power cyclotomic rings. The complexity is $O(n^3 \log^2 n)$ quantum gates and $O(n^2 \log n)$ qubits, where $n$ is the ring degree. This removes the exponential overhead previously associated with the Biasse-Song algorithm.
• Tight Approximation Factor Analysis: The authors derive an exact approximation factor $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$. They prove that the variance $\sigma_d$ of the log-embedding is $O(1)$ and independent of the modulus $q$.
• Verification of Class Number: The work relies on the proof (from Part I) that the class number of the maximal real subfield is trivial ($h^+_k = 1$) for all $k \le 12$, ensuring every ideal is principal.
• Extension to Multiple Schemes: The framework is extended beyond ML-KEM to analyze Falcon, Hawk, and NTRU variants over 2-power cyclotomics, demonstrating that the same algebraic weaknesses apply.

Results
The authors provide concrete security estimates for standardized parameter sets:

• ML-KEM-1024: The attack achieves a median approximation factor $\gamma_{med} \approx 21$ and a 99th percentile factor $\gamma_{99\%} \approx 103$. Both values are significantly below the security threshold of $q/2 = 1665$. The success probability is estimated at $\ge 0.99$ for $d \le 3$ and $\ge 0.90$ for $d=4$, with failure probability reducible to $< 10^{-6}$ via repetition.
• Resource Estimates: For ML-KEM-1024 ($n=256$), the attack requires approximately $2^{27}$ logical gates and $1.4 \times 10^6$ physical qubits (assuming surface code with distance 30).
• Other Schemes:
  • Falcon: The attack breaks Falcon-512 and Falcon-1024 with margins of $72\times$ and $63\times$ respectively.
  • Hawk: The attack breaks Hawk-512 and Hawk-1024. Hawk-256 is conditionally broken; while the formal 99% bound exceeds the threshold, empirical simulations show a success rate of 99.99%.
  • NTRU: The attack applies to NTRU-HPS and NTRU-HRSS variants over 2-power cyclotomic rings, achieving margins ranging from $11\times$ to $45\times$.

Significance and Claims
The paper claims to resolve the open questions regarding the CDPR attack by demonstrating that:

1. The approximation factor is small enough to break all standardized ML-KEM, Falcon, Hawk, and NTRU parameter sets over 2-power cyclotomic rings under a quantum attack.
2. The PIP can be solved in true polynomial time ($O(n^3 \log^2 n)$) without hidden exponential factors or reliance on unproven number-theoretic conjectures like GRH.
3. The algebraic structure of 2-power cyclotomic rings allows a quantum adversary to reduce the approximation factor from super-polynomial ($\approx 2^{54}$ in prior estimates) to sub-polynomial ($\approx 2^{21}$), effectively breaking the security assumptions of these post-quantum candidates.

The authors note that while the attack is probabilistic, the failure probability is low and can be mitigated by independent repetitions. They emphasize that the results rely on the specific algebraic properties of 2-power cyclotomic rings and the triviality of the class number for $k \le 12$.