Paper 2023/1824

Learning with Errors over Group Rings Constructed by Semi-direct Product

Jiaqi Liu
Fang-Wei Fu

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.

Available format(s)
Public-key cryptography
Publication info
Learning with errorsGroup ringsSemi-direct productGroup representationsLattice-based cryptography
Contact author(s)
ljqi @ mail nankai edu cn
fwfu @ nankai edu cn
2023-12-01: last of 2 revisions
2023-11-28: received
See all versions
Short URL
No rights reserved


      author = {Jiaqi Liu and Fang-Wei Fu},
      title = {Learning with Errors over Group Rings Constructed by Semi-direct Product},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1824},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.