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
  • $\begingroup$ @JyrkiLahtonen: Thanks for you reply. I've been able to construct a representation of $RG$ as a vector space over $F_p$ since analysing the product of $v.u$ where $v,u\in RG$ yields an algebraic relationship where every $a \in RG$ is a $nxn$ matrix where $n$ is $\vert G \vert$, this is well understood examining the group's multiplication table. Now, are you talking about of decomposing $R[G]$ into irreducible parts depending on the coprimality of the characteristic of $R$ and the group's order $\vert G \vert$? What could you obtain if Alice gives you an arbitrary element in $R[G]$? $\endgroup$ – kub0x Aug 28 at 9:08
  • $\begingroup$ By the way this paper researchgate.net/publication/… illustrates a ton of what I've been reading and discovering so far, for example the construction of the matrix ring from RG, and the applicable cases for cyclic and dihedral groups (which I enjoy doing on Mathematica). I think it worths a read for anyone interested on group rings and crypto. $\endgroup$ – kub0x Aug 28 at 15:10

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.