The learning with errors ( \(\textsf{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 \(\textsf{LWE}\) problem called Group ring \(\textsf{LWE}\) ( \(\textsf{GR} \text{- }\textsf{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- \(\textsf{LWE}\) problem described in [35], the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring- \(\textsf{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 ( \(\textsf{SIVP}\) ) on ideal lattices with polynomial approximation factor to the search version of \(\textsf{GR} \text{- }\textsf{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 \(\textsf{SIVP}\) problem is directly reduced to the (average-case) decision \(\textsf{GR} \text{- }\textsf{LWE} \) problem. The pseudorandomness of \(\textsf{GR} \text{- }\textsf{LWE} \) samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.
