Middle-Product Learning with Rounding Problem and its Applications

Shi Bai; Katharina Boudgoust; Dipayan Das; Adeline Roux-Langlois; Weiqiang Wen; Zhenfei Zhang

Paper 2019/1001

Middle-Product Learning with Rounding Problem and its Applications

Shi Bai, Katharina Boudgoust, Dipayan Das, Adeline Roux-Langlois, Weiqiang Wen, and Zhenfei Zhang

Abstract

At CRYPTO 2017, Rosca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (MP-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning With Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called Middle-Product Computational Learning With Rounding, an adaption of the computational LWR problem over rings, introduced by Chen et al. at ASIACRYPT 2018. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in ASIACRYPT 2019
DOI: 10.1007/978-3-030-34578-5_3
Keywords: LWE LWR Middle-Product Public Key Encryption
Contact author(s): katharina boudgoust @ irisa fr
History: 2020-08-24: last of 2 revisions; 2019-09-05: received; See all versions
Short URL: https://ia.cr/2019/1001
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1001,
      author = {Shi Bai and Katharina Boudgoust and Dipayan Das and Adeline Roux-Langlois and Weiqiang Wen and Zhenfei Zhang},
      title = {Middle-Product Learning with Rounding Problem and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1001},
      year = {2019},
      doi = {10.1007/978-3-030-34578-5_3},
      note = {\url{https://eprint.iacr.org/2019/1001}},
      url = {https://eprint.iacr.org/2019/1001}
}