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

Ming-Xing Luo

arxiv: 2605.17412 · v2 · pith:HMYZ6MJEnew · submitted 2026-05-17 · 🪐 quant-ph · cs.CR· math.CO· math.RA

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

Ming-Xing Luo This is my paper

Pith reviewed 2026-05-20 13:03 UTC · model grok-4.3

classification 🪐 quant-ph cs.CRmath.COmath.RA

keywords module-LWEquantum attack2-power cyclotomic ringsML-KEMprincipal ideal problemtower decompositionlattice-based cryptographypost-quantum security

0 comments

The pith

A quantum algorithm using tower decomposition breaks module-LWE over 2-power cyclotomics for standardized schemes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a quantum attack on module lattice schemes such as ML-KEM that rely on 2-power cyclotomic rings. By applying a tower decomposition to the principal ideal problem across successive cyclotomic extensions starting from the rationals, the module learning with errors instance reduces to subproblems solvable in polynomial time on a quantum computer. The resulting approximation factor for ML-KEM-1024 remains at most 21, which is less than half the modulus value of 1665, and the attack succeeds with probability at least 0.99. This extends to show breaks for Falcon, Hawk, and NTRU parameter sets as well. The algorithm requires O(n^3 log squared n) quantum gates and O(n^2 log n) qubits.

Core claim

Combining with Parts I-III, the tower decomposition of the Principal Ideal Problem through the chain Q subset Q(zeta_8) subset ... subset Q(zeta_{2^k}) yields a polynomial-time quantum algorithm that solves the Module-LWE problem over these rings with approximation factor gamma less than or equal to 21, which is smaller than q/2 for the parameters of ML-KEM-1024, achieving success probability at least 0.99 and thereby breaking the security of ML-KEM, Falcon, Hawk, NTRU-HPS and NTRU-HRSS.

What carries the argument

Tower decomposition of the Principal Ideal Problem (PIP) through the chain of 2-power cyclotomic fields, which enables the reduction of module-LWE to efficiently solvable instances.

If this is right

ML-KEM with all standardized parameters is broken by this quantum attack.
Falcon, Hawk, NTRU-HPS, and NTRU-HRSS are similarly broken.
The quantum algorithm has time complexity O(n^3 log^2 n) gates and uses O(n^2 log n) qubits.
Success probability is at least 0.99 for the verified parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result indicates that lattice-based cryptography over 2-power cyclotomic rings may be insecure against quantum attacks even if classical attacks are resisted.
Designers of future post-quantum schemes might need to consider alternative ring structures to avoid this decomposition.
Verification of the approximation factor suggests the attack is practical enough to threaten current standards if a large enough quantum computer is built.

Load-bearing premise

The tower decomposition of the Principal Ideal Problem through the chain Q subset Q(zeta_8) subset ... subset Q(zeta_{2^k}) yields a polynomial-time quantum algorithm costing O(n^3 log^2 n) gates.

What would settle it

An observation that the approximation factor exceeds 21 or the success probability falls below 0.99 for ML-KEM-1024 parameters after applying the tower decomposition would falsify the central claim.

read the original abstract

We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies $\gamma\le 21 < q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(\zeta_8)\subset\cdots\subset \Q(\zeta_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3 \log^2 n)$ gates, $O(n^2 \log n)$ qubits, and poly$(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Claims a quantum poly-time break on ML-KEM via tower decomposition of the PIP but supplies no visible error-propagation analysis or reduction steps to back the gamma bound.

read the letter

The main point is that this Part IV claims a polynomial-time quantum algorithm for Module-LWE over 2-power cyclotomic rings that produces an approximation factor at most 21 for ML-KEM-1024, below q/2, with success probability at least 0.99. It extends the same approach to Falcon, Hawk, and the NTRU variants and states an overall gate count of O(n^3 log^2 n). If the reduction actually holds, that would be a concrete attack on the current NIST lattice standards. The tower decomposition from Q through successive Q(zeta_{2^k}) extensions is presented as the key technical step that makes the cost polynomial while controlling the approximation factor. The paper checks the numbers against the standardized parameter sets and reports the concrete bounds, which is useful bookkeeping if the underlying math is sound. It also ties the result back to the earlier parts of the series for the overall attack structure. The soft spots are in the reduction itself. The abstract and the supplied sections give no explicit mapping of how the module rank, the error distribution, or the lattice dimension transform level by level, nor any bound showing that approximation errors do not accumulate past the claimed gamma of 21. The stress-test note on missing error-propagation analysis across the tower levels matches what is visible. Without those steps, it is impossible to verify that the final short-vector instance stays inside the required range rather than inflating. There is also little direct comparison to earlier quantum algorithms for ideal lattices or cyclotomic fields, so the degree of novelty is hard to judge from the text given. This is written for specialists already following the series on module-lattice attacks. A reader who has the prior parts might extract the parameter checks, but the work is not self-contained and the central claim rests on unshown derivations. I would not send it to peer review in its current form; the mathematical steps need to be written out and checked before a referee should spend time on it.

Referee Report

3 major / 2 minor

Summary. The manuscript presents a quantum attack on Module-LWE over 2-power cyclotomic rings. Combining results from Parts I-III, it claims an algorithm via tower decomposition of the Principal Ideal Problem through the chain Q ⊂ Q(ζ₈) ⊂ ⋯ ⊂ Q(ζ_{2^k}) that achieves approximation factor γ ≤ 21 < q/2 = 1665 for ML-KEM-1024 with success probability ≥ 0.99. The attack is extended to Falcon, Hawk, and NTRU, concluding that all standardized parameter sets are broken, with stated costs O(n³ log² n) quantum gates, O(n² log n) qubits, and poly(n) classical bits.

Significance. If the approximation factor bound and success probability hold with the stated polynomial quantum resources, the result would be highly significant, as it would imply that standardized lattice-based post-quantum schemes including ML-KEM are insecure against quantum attacks. The explicit complexity bounds and extension to multiple schemes are strengths if the underlying reductions are rigorous.

major comments (3)

[Abstract] Abstract: The verification that the resulting approximation factor satisfies γ ≤ 21 for ML-KEM-1024 is asserted without supplying derivation steps, error propagation analysis, or explicit reduction showing how the factor is obtained from the tower decomposition of the Principal Ideal Problem.
[Tower decomposition section] Tower decomposition analysis: The claimed O(n³ log² n) gate count and γ ≤ 21 bound require an explicit mapping of module rank, error distribution, and lattice dimension through each extension Q(ζ_{2^j}) while keeping accumulated approximation error below q/2; no such propagation bound is provided.
[Success probability analysis] Success probability: The stated success probability ≥ 0.99 lacks a probabilistic analysis accounting for failure modes in the quantum algorithm or inflation of the approximation factor across tower levels.

minor comments (2)

[Notation and preliminaries] Clarify the precise definition of the tower levels and extension degrees for readers unfamiliar with the series.
[Algorithm description] Add explicit cross-references to the specific theorems from Parts I-III that are combined in the algorithm.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments on our manuscript. We will revise the paper to address the concerns regarding missing derivations and analyses.

read point-by-point responses

Referee: [Abstract] Abstract: The verification that the resulting approximation factor satisfies γ ≤ 21 for ML-KEM-1024 is asserted without supplying derivation steps, error propagation analysis, or explicit reduction showing how the factor is obtained from the tower decomposition of the Principal Ideal Problem.

Authors: We agree that the abstract would benefit from additional context. In the revised manuscript, we will include a concise outline of the key derivation steps from the tower decomposition of the Principal Ideal Problem, referencing the combination with Parts I-III. This will clarify how the approximation factor γ ≤ 21 is obtained for ML-KEM-1024 parameters. revision: yes
Referee: [Tower decomposition section] Tower decomposition analysis: The claimed O(n³ log² n) gate count and γ ≤ 21 bound require an explicit mapping of module rank, error distribution, and lattice dimension through each extension Q(ζ_{2^j}) while keeping accumulated approximation error below q/2; no such propagation bound is provided.

Authors: The referee is correct that an explicit propagation bound is essential. We will add a detailed analysis in the tower decomposition section that maps the module rank, error distribution, and lattice dimension at each level of the extension chain Q(ζ_{2^j}). We will derive bounds ensuring the accumulated approximation error stays below q/2, which supports both the γ ≤ 21 claim and the O(n³ log² n) gate complexity. revision: yes
Referee: [Success probability analysis] Success probability: The stated success probability ≥ 0.99 lacks a probabilistic analysis accounting for failure modes in the quantum algorithm or inflation of the approximation factor across tower levels.

Authors: We acknowledge the need for a more rigorous probabilistic analysis. In the revision, we will provide an analysis that accounts for potential failure modes in the quantum steps and the possible inflation of the approximation factor through the tower levels. This will demonstrate that the overall success probability remains at least 0.99 for the standardized parameters. revision: yes

Circularity Check

1 steps flagged

Central γ ≤ 21 bound and success probability reduce to self-cited Parts I-III without independent verification

specific steps

self citation load bearing [Abstract]
"Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies γ ≤ 21 < q/2=1665 for ML-KEM-1024, with a success probability ≥ 0.99. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain Q ⊂ Q(ζ8) ⊂ ⋯ ⊂ Q(ζ_{2^k}) which yields a polynomial-time quantum algorithm costing O(n^3 log² n) gates, O(n^2 log n) qubits, and poly(n) classical bit operations."

The verification step that produces the concrete security-breaking bound γ ≤ 21 and probability ≥ 0.99 is justified solely by reference to the author's own prior Parts I-III. No independent derivation, external benchmark, or error-propagation analysis across the tower levels is supplied in the abstract; the central claim therefore reduces to the series' internal constructions.

full rationale

The paper's load-bearing claims (γ ≤ 21 with prob ≥ 0.99 breaking ML-KEM-1024 and related schemes) are explicitly obtained by combining with Parts I-III. The tower decomposition is asserted to produce the stated gate count and approximation factor, yet the specific numerical bound and probability are not re-derived from first principles or external benchmarks in the provided text; they inherit from the prior self-authored parts. This creates partial circularity in the derivation chain while the overall algorithm description retains some independent structure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the unproven efficiency of the tower decomposition for the principal ideal problem in 2-power cyclotomic rings; no free parameters or invented entities are explicitly listed in the abstract.

axioms (1)

domain assumption Tower decomposition of PIP through Q ⊂ Q(ζ8) ⊂ ⋯ ⊂ Q(ζ_{2^k}) yields polynomial-time quantum algorithm
Invoked to obtain O(n^3 log² n) gate complexity and the stated approximation factor.

pith-pipeline@v0.9.0 · 5724 in / 1296 out tokens · 57569 ms · 2026-05-20T13:03:20.560891+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain Q ⊂ Q(ζ₈) ⊂ ⋯ ⊂ Q(ζ_{2^k})

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.