Cryptology ePrint Archive: Report 2019/1179

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

Ron Steinfeld and Amin Sakzad and Raymond K. Zhao

Abstract: Middle-Product Learning With Errors (MP-LWE) is a variant of the LWE problem introduced at CRYPTO 2017 by Rosca et al [RSSS17]. Asymptotically, the theoretical results of [RSSS17] 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, [RSSS17] 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 [RSSS17]. We also show and analyze an optimised cryptanalysis of MP-LWE that narrows the complexity gap to the above security proof. 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.

Category / Keywords: public-key cryptography / public-key cryptography / middle-product learning with errors (MP-LWE), lattice-based cryptography, quantum-resistant cryptography, public-key encryption, KEM, cryptography implementation.

Original Publication (with minor differences): Designs, Codes and Cryptography (DCC)

Date: received 9 Oct 2019, last revised 9 Oct 2019

Contact author: ron steinfeld at monash edu

Available format(s): PDF | BibTeX Citation

Note: This is the author version of a paper published in the journal Designs, Codes and Cryptography (DCC). This version does not include minor revisions made to address the DCC reviewers' comments.

Version: 20191010:125611 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]