Middle-Products of Skew Polynomials and Learning with Errors

Cong Ling; Andrew Mendelsohn

Paper 2023/1901

Middle-Products of Skew Polynomials and Learning with Errors

Cong Ling, Imperial College London

Andrew Mendelsohn

, Imperial College London

Abstract

We extend the middle product to skew polynomials, which we use to define a skew middle-product Learning with Errors (LWE) variant. We also define a skew polynomial LWE problem, which we connect to Cyclic LWE (CLWE), a variant of LWE in cyclic division algebras. We then reduce a family of skew polynomial LWE problems to skew middle-product LWE, for a family which includes the structures found in CLWE. Finally, we give an encryption scheme and demonstrate its IND-CPA security, assuming the hardness of skew middle-product LWE.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. IMACC 2023
DOI: 10.1007/978-3-031-47818-5_11
Keywords: middle product LWE cyclic division algebras skew polynomials
Contact author(s): c ling @ imperial ac uk
andrew mendelsohn18 @ imperial ac uk
History: 2023-12-12: approved; 2023-12-11: received; See all versions
Short URL: https://ia.cr/2023/1901
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1901,
      author = {Cong Ling and Andrew Mendelsohn},
      title = {Middle-Products of Skew Polynomials and Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1901},
      year = {2023},
      doi = {10.1007/978-3-031-47818-5_11},
      note = {\url{https://eprint.iacr.org/2023/1901}},
      url = {https://eprint.iacr.org/2023/1901}
}