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 productLWEcyclic division algebrasskew 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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2023/1901}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.