Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2311.15868 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914380264767488 |
|---|---|
| author | Liu, Jiaqi Fu, Fang-Wei |
| author_facet | Liu, Jiaqi Fu, Fang-Wei |
| contents | 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 \emph{Group ring} \LWE ($\GRLWE$). 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 $\GRLWE$. 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 $\GRLWE$ problem. The pseudorandomness of $\GRLWE$ samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15868 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Learning with Errors over Group Rings Constructed by Semi-direct Product Liu, Jiaqi Fu, Fang-Wei Cryptography and Security Information Theory 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 \emph{Group ring} \LWE ($\GRLWE$). 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 $\GRLWE$. 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 $\GRLWE$ problem. The pseudorandomness of $\GRLWE$ samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems. |
| title | Learning with Errors over Group Rings Constructed by Semi-direct Product |
| topic | Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2311.15868 |