Practical MP-LWE-based encryption balancing security-risk versus efficiency.

Middle-product learning with errors ( MP - LWE ) is a variant of the LWE problem introduced at CRYPTO 2017 by Rosca et al. (Advances in cryptology—CRYPTO, Springer, Berlin, 2017). Asymptotically, the theoretical results of Rosca et al. (2017) suggest that MP - LWE gives lattice-based public-key cryptosystems offering a 'security-risk vs. efficiency' trade-off: higher performance than cryptosystems based on unstructured lattices (LWE problem) and lower risk than cryptosystems based on structured lattices (Polynomial/Ring LWE problem). However, although promising in theory, Rosca et al. (2017) left the practical implications of MP - LWE for lattice-based cryptography unclear. In this paper, we show how to build practical public-key cryptosystems with strong security guarantees based on MP - LWE . On the implementation side, we present optimised fast algorithms for computing the middle-product operation over polynomial rings Z q [ x ] , the dominant computation for MP - LWE -based cryptosystems. On the security side, we show how to obtain a nearly tight security proof for MP - LWE from the hardest Polynomial LWE problem over a large family of rings, improving on the loose reduction of Rosca et al. (2017). We also show and analyze an optimised cryptanalysis of MP - LWE that narrows the complexity gap between best known attacks on MP - LWE and Polynomial LWE . To evaluate the practicality of MP - LWE , we apply our results to construct, implement and optimise parameters for a practical MP - LWE -based public-key cryptosystem, Titanium , and compare its benchmarks to other lattice-based systems. Our results show that MP - LWE offers a new 'security-risk vs. efficiency' trade-off in lattice-based cryptography in practice, not only asymptotically in theory. [ABSTRACT FROM AUTHOR]