analiza aiqbench
This research extends quantum lattice reduction attacks from ideal to module lattices over cyclotomic rings, achieving a Hermite factor that matches the ideal case while maintaining a rank-independent reduction factor. By reformulating sign selection as a mixed-integer linear program and optimizing rounding precision via the Chinese Remainder Theorem, the authors eliminate previous heuristic discrepancies and enable bounded-precision implementations. These theoretical advances directly impact the security assessment of MLWE-based cryptographic schemes against future quantum adversaries.
Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection
arXiv:2604.22900v2 Announce Type: replace-cross 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 $\alpha_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 r n \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 $\Theta(\sqrt{nk})$. All results build on the class number condition $h_k^+=1$ established in Part I of this series.
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 $\alpha_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 r n \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 $\Theta(\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 this http URL does not affect all the polynomical algorithms in Part IV. For simulation video see the comment of Part IV in this series
Cryptography and Security (cs.CR); Information Theory (cs.IT); Quantum Physics (quant-ph)
arXiv:2604.22900 [cs.CR]
(or arXiv:2604.22900v2 [cs.CR] for this version)
Text integral sub licența deschisă a publicației · 231 cuvinte
Subiecte conexe
Elephant in the Fridge: Constant-Memory Frame Packing for Long Video Understanding
arXiv · 14 oct. 2026
Loop-dependent entangling holonomies in localized topological quartets
Journal of Quantum (JQUANT), SISSA · 22 oct. 2026
Assessing the impact of dimensionality reduction on clustering performance - a systematic study
arXiv · 24 sept. 2026
Selective Tie Learning: Mitigating Spurious Correlations in Preference Optimization
arXiv · 27 oct. 2026