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 and lower risk than cryptosystems based on structured lattices (Polynomial/Ring LWE. 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 Zq[x], the dominant computation for MP-LWE. 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 asand Polynomial LWE. To evaluate the practicality of P-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.