Description
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as `Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens-Davidowitz, CRYPTO 2020) confirmed the existence of such module variants of LLL and block-reduction algorithms, but focus only on provable worst-case asymptotic behavior.
In this work, we present a concrete average-case analysis of module-lattice reduction. Specifically, we address the question of the expected slope after running module-BKZ, and pinpoint the discriminant $\Delta_K$ of the number field at hand as the main quantity driving this slope. We convert this back into a gain or loss on the blocksize $\beta$: module-BKZ in a number field $K$ of degree $d$ requires an SVP oracle of dimension $\beta + \log(|\Delta_K| / d^d)\beta /(d\log \beta) + o(\beta / \log \beta)$ to reach the same slope as unstructured BKZ with blocksize $\beta$. This asymptotic summary hides further terms that we predict concretely using experimentally verified heuristics. Incidentally, we provide the first open-source implementation of module-BKZ for some cyclotomic fields.
For power-of-two cyclotomic fields, we have $|\Delta_K| = d^d$, and show that module-BKZ requires a blocksize larger than its unstructured counterpart by $d-1+o(1)$. On the contrary, for all other cyclotomic fields we have $|\Delta_K| < d^d$, so module-BKZ provides a sublinear $\Theta(\beta/\log \beta)$ gain on the required blocksize, yielding a subexponential speedup of $\exp(\Theta(\beta/\log \beta))$.
Practical infos
Next sessions
-
Module Learning With Errors and Structured Extrapolated Dihedral Cosets
Speaker : Jinwei Zheng - Télécom Paris
The Module Learning With Errors (MLWE) problem is the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA, which have been selected by NIST for post-quantum cryptography standardization. Understanding its quantum hardness is crucial for assessing the security of these standardized schemes. Inspired by the equivalence between LWE and[…]-
Cryptography
-
-
European Cyber Week: atelier cryptographie post-quantique
Dans la continuité des éditions 2021, 2022 et 2024, la DGA — en partenariat avec CREACH LABS et avec le soutien de l'ANSSI, de l'IRISA, de l'IRMAR et du Pôle d'Excellence Cyber — organise la 4e édition de l'atelier consacré à la cryptographie post-quantique dans le cadre de l'European Cyber Week 2026. Attention, il faut s'inscrire (gratuitement) au préalable — s'inscrire à la conférence Les[…] -
Journée post-quantique du séminaire cryptographie
Journée scientifique sur la cryptographie post-quantique dans la foulée de l'European Cyber Week avec des exposés plus techniques que ceux de l'ECW.