  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.
