  The Learning with Errors (LWE) problem has been widely utilized as a
foundation for numerous cryptographic tools over the years. In this study, we
focus on an algebraic variant of the LWE problem called Group ring LWE
(GR-LWE). We select group rings (or their direct summands) that underlie
specific families of finite groups constructed by taking the semi-direct
product of two cyclic groups. Unlike the Ring-LWE problem described in
\cite{lyubashevsky2010ideal}, the multiplication operation in the group rings
considered here is non-commutative. As an extension of Ring-LWE, it maintains
computational hardness and can be potentially applied in many cryptographic
scenarios. In this paper, we present two polynomial-time quantum reductions.
Firstly, we provide a quantum reduction from the worst-case shortest
independent vectors problem (SIVP) in ideal lattices with polynomial
approximate factor to the search version of GR-LWE. This reduction requires
that the underlying group ring possesses certain mild properties; Secondly, we
present another quantum reduction for two types of group rings, where the
worst-case SIVP problem is directly reduced to the (average-case) decision
GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this
reduction can be consequently leveraged to construct semantically secure
public-key cryptosystems.
