Paper 2019/1179

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

Ron Steinfeld, 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.

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Designs, Codes and Cryptography (DCC)
DOI
10.1007/s10623-019-00654-5
Keywords
public-key cryptographylattice-based cryptographyquantum-resistant cryptographypublic-key encryptionKEMcryptography implementation.
Contact author(s)
ron steinfeld @ monash edu
History
2019-10-10: received
Short URL
https://ia.cr/2019/1179
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1179,
      author = {Ron Steinfeld and Amin Sakzad and Raymond K.  Zhao},
      title = {Practical MP-LWE-based encryption balancing security-risk vs. efficiency},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1179},
      year = {2019},
      doi = {10.1007/s10623-019-00654-5},
      note = {\url{https://eprint.iacr.org/2019/1179}},
      url = {https://eprint.iacr.org/2019/1179}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.