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 $$\varDelta _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 + \ln (|\varDelta _K| / d^d)\beta /(d\ln \beta ) + o(\beta / \ln \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 conductors, we have $$|\varDelta _K| = d^d$$ , and conclude that module-BKZ needs a blocksize larger than its unstructured counterpart. On the contrary, for all other cyclotomic fields, $$|\varDelta _K| < d^d$$ , so module-BKZ provides a sublinear $$\varTheta (\beta /\ln \beta )$$ gain on the required blocksize, yielding a subexponential speedup of $$\exp (\varTheta (\beta /\ln \beta ))$$ .

In this paper, we extend Inner-Product Functional Encryption (IPFE), where there is just a vector in the key and a vector in the single sender's ciphertext, to two-client ciphertexts. More precisely, in our two-client functional encryption scheme, there are two Data Providers who can independently encrypt vectors x and y for a data consumer who can, from a functional decryption key associated to a vector α, compute ∑αi xiyi = x ⋅ Diag(α) ⋅ yT. Ciphertexts are linear in the dimension of the vectors, whereas the functional decryption keys are of constant size. We study two interesting particular cases: