Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910163838959616 |
|---|---|
| author | Luo, Ming-Xing |
| author_facet | Luo, Ming-Xing |
| contents | We extend the CDPR lattice reduction algorithm from ideal to module lattices, leveraging the trace orthogonality of the power basis to decompose the module into rank-1 submodules and applying CDPR independently to each. This base module reduction achieves a Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matching the ideal case, with a module reduction factor $O(1)$ independent of the rank, under a balance hypothesis automatically satisfied for MLWE-distributed bases. To control precision, we introduce CRT-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding error and yielding a bounded-precision implementation. We further reformulate the CDPR sign-selection subproblem as a mixed-integer linear program, determining the optimal balanced discrepancy to be a universal constant $δ^*\approx 0.4407$. All results build on the class number one condition $h_k^+=1$ established in Part I of this series. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22900 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection Luo, Ming-Xing Cryptography and Security Information Theory Quantum Physics We extend the CDPR lattice reduction algorithm from ideal to module lattices, leveraging the trace orthogonality of the power basis to decompose the module into rank-1 submodules and applying CDPR independently to each. This base module reduction achieves a Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matching the ideal case, with a module reduction factor $O(1)$ independent of the rank, under a balance hypothesis automatically satisfied for MLWE-distributed bases. To control precision, we introduce CRT-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding error and yielding a bounded-precision implementation. We further reformulate the CDPR sign-selection subproblem as a mixed-integer linear program, determining the optimal balanced discrepancy to be a universal constant $δ^*\approx 0.4407$. All results build on the class number one condition $h_k^+=1$ established in Part I of this series. |
| title | Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection |
| topic | Cryptography and Security Information Theory Quantum Physics |
| url | https://arxiv.org/abs/2604.22900 |