Paper 2019/680

Non-Commutative Ring Learning With Errors From Cyclic Algebras

Charles Grover
Andrew Mendelsohn
Cong Ling
Roope Vehkalahti
Abstract

The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of `structured' LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. The proposed construction is both more efficient than Module LWE and conjecturally more secure than Ring LWE, the best of both worlds. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem. As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding.

Note: Minor difference, with modulus switching removed in the journal version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in JOC 2022
Keywords
Lattices Public-Key Cryptography Learning With Errors Non-Commutative Rings Modules.
Contact author(s)
c grover15 @ imperial ac uk
andrew mendelsohn18 @ imperial ac uk
c ling @ imperial ac uk
roope vehkalahti @ aalto fi
History
2022-06-23: last of 7 revisions
2019-06-11: received
See all versions
Short URL
https://ia.cr/2019/680
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/680,
      author = {Charles Grover and Andrew Mendelsohn and Cong Ling and Roope Vehkalahti},
      title = {Non-Commutative Ring Learning With Errors From Cyclic Algebras},
      howpublished = {Cryptology ePrint Archive, Paper 2019/680},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/680}},
      url = {https://eprint.iacr.org/2019/680}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.