Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

Abstract

We extend the CDPR's quantum attack from ideal lattices to module lattices over $2^k$-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-$d$ module into mutually orthogonal rank-$1$ submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor $\exp (\tilde{O}(\sqrt{n}))$ matches the ideal case, with a module reduction factor $\hat{I}{\pm }_d=O(1)$ independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from $n/2$ to $\le 1$ at cost $O(d^{2}rn\log n)$. Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all $k$ ($\approx 0.4407$ for all tested $k\le 12$, conjecturally universal). This replaces the previous heuristic discrepancy $\hat{I}˜(\sqrt{nk})$. All results build on the class number condition $h_k^{+}=1$ established in Part I of this series.

30 pages, add new results and proofs of previous simulations and examples. The key change is alpha_d=sqrt C which is changed into 1.3346.This does not affect all the polynomical algorithms in Part IV. For simulation video see the comment of Part IV in this series