Welcome to the resource topic for 2025/1904
Title:
Predicting Module-Lattice Reduction
Authors: Léo Ducas, Lynn Engelberts, Paola de Perthuis
Abstract: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 conclude 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)).
ePrint: https://eprint.iacr.org/2025/1904
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .