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

Ron Steinfeld, Amin Sakzad, Raymond K. Zhao

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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 Zq[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.

Original languageEnglish
Number of pages38
JournalDesigns Codes and Cryptography
DOIs
Publication statusAccepted/In press - 22 Jun 2019

Keywords

  • Cryptography implementation
  • KEM
  • Lattice-based cryptography
  • Middle-product learning with errors (MP-LWE)
  • Public-key encryption
  • Quantum-resistant cryptography

Cite this

@article{0973cf3889e6422ba7cb03f0406138a8,
title = "Practical MP-LWE -based encryption balancing security-risk versus efficiency",
abstract = "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 Zq[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.",
keywords = "Cryptography implementation, KEM, Lattice-based cryptography, Middle-product learning with errors (MP-LWE), Public-key encryption, Quantum-resistant cryptography",
author = "Ron Steinfeld and Amin Sakzad and Zhao, {Raymond K.}",
year = "2019",
month = "6",
day = "22",
doi = "10.1007/s10623-019-00654-5",
language = "English",
journal = "Designs Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer-Verlag London Ltd.",

}

Practical MP-LWE -based encryption balancing security-risk versus efficiency. / Steinfeld, Ron; Sakzad, Amin; Zhao, Raymond K.

In: Designs Codes and Cryptography, 22.06.2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Steinfeld, Ron

AU - Sakzad, Amin

AU - Zhao, Raymond K.

PY - 2019/6/22

Y1 - 2019/6/22

N2 - 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 Zq[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.

AB - 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 Zq[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.

KW - Cryptography implementation

KW - KEM

KW - Lattice-based cryptography

KW - Middle-product learning with errors (MP-LWE)

KW - Public-key encryption

KW - Quantum-resistant cryptography

UR - http://www.scopus.com/inward/record.url?scp=85068167202&partnerID=8YFLogxK

U2 - 10.1007/s10623-019-00654-5

DO - 10.1007/s10623-019-00654-5

M3 - Article

JO - Designs Codes and Cryptography

JF - Designs Codes and Cryptography

SN - 0925-1022

ER -