Crypto Team – CASCADE (original) (raw)

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'e, 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 DeltaK\Delta_KDeltaK 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\betabeta: module-BKZ in a number field KKK of degree ddd 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\betabeta. 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 ∣DeltaK∣=dd|\Delta_K| = d^d∣DeltaK∣=dd, and conclude that module-BKZ requires a blocksize larger than its unstructured counterpart by d−1+o(1)d-1+o(1)d−1+o(1). On the contrary, for all other cyclotomic fields we have ∣DeltaK∣<dd|\Delta_K| < d^d∣DeltaK∣<dd, so module-BKZ provides a sublinear Theta(beta/logbeta)\Theta(\beta/\log \beta)Theta(beta/logbeta) gain on the required blocksize, yielding a subexponential speedup of exp(Theta(beta/logbeta))\exp(\Theta(\beta/\log \beta))exp(Theta(beta/logbeta)).

Joint work with Lynn Engelberts and Paola de Perthuis.