3
$\begingroup$

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This structure is very similar to a polynomial quotient ring $F_q[x]/f(x)$ taken as a vector space, since the number of distinct tuples is $q^k$, and $k$ is the degree of $f(x)$.

From now I immediately start to think on applications on Cryptography. Been experimenting with it and multiplication is trivial to compute via programming. I'm able to enumerate the group of units but for now with trivial examples using naive methods (i.e: exponentiation). But for example, I have not tried to examine what happens when $G$ is a matrix group. Also we can try to figure out how to use this structure as the platform group for existing schemes, so algorithms for computing necessary transformations (trapdoor, public/private generation etc) must have a nice complexity.

Is there any scheme that works with group rings in any of its parts?

$\endgroup$
  • $\begingroup$ You may want to consider cryptographic schemes with security reductions to RingLWE problems. Often the ring is a cyclotomic number field of the form $Z_q[x]/ f_n(x)$ where $f_n(x)$ is the nth-cyclotomic polynomial. $\endgroup$ – shaun1010 Jun 24 at 3:19
  • $\begingroup$ @shaun1010: Thanks. I'll review that for sure. $\endgroup$ – kub0x Jun 24 at 10:21
  • $\begingroup$ What is the underlying difficult problem in these rings? If we first assume that $\gcd(|G|,q)=1$, then $RG$ can be split into components that are matrix rings over some extension fields $\Bbb{F}_{q^r}$. If we further assume that $G$ is abelian, then those matrix rings have size one, i.e. they are fields. If that $\gcd$ is higher, then we get more nilpotent stuff in the ring. Anyway, my point is that the hard problem should remain hard in a matrix ring for the group ring to be an attractive playground. $\endgroup$ – Jyrki Lahtonen Jul 6 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.