Non-abelian discrete logarithm

Section 7 Non-abelian discrete logarithm

The discrete logarithm problem forms the basis of many cryptographic primitives. Ilić and Magliveras showed that the generalized discrete logarithm problem in certain non-abelian groups is easy to solve. Here we provide details and numerical examples based on results by Ilić and Magliveras.

Subsection 7.1 Discrete logarithm with special generators

The general linear group of degree \(n\) over \(\mathbb{F}_q\) (denoted by \(GL(n,\mathbb{F}_q)\)) is the set of \(n\times n\) invertible matrices, together with the operation of ordinary matrix multiplication. The special linear group \(SL(n,\mathbb{F}_q)\) of degree \(n\) over \(\mathbb{F}_q\) is the set of \(n\times n\) matrices with determinant 1. The center \(Z(GL(n,\mathbb{F}_q))\) of \(GL(n,\mathbb{F}_q)\) consists of all matrices of the form

\begin{equation*} \lambda I, \end{equation*}

where \(\lambda\in\mathbb{F}_q^*\) and \(I\) is the \(n\times n\) identity matrix. The quotient group

\begin{equation*} PSL(n,\mathbb{F}_q) = SL(n,\mathbb{F}_q)/Z(SL(n,\mathbb{F}_q)) \end{equation*}

is called the projective special linear group of degree \(n\) over \(\mathbb{F}_q.\) Consider the group \(PSL(2,\mathbb{F}_p)\) where \(p\) is an odd prime. Let

\begin{equation*} A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. \end{equation*}

These matrices are of order \(p\) and non-commuting. We will work in the group \(G=<A,B>.\) Suppose that

\begin{equation*} M=\begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} \ \in \ G, \; m_{11}, m_{12}, m_{21}, m_{22} \in \mathbb{F}_{p}. \end{equation*}

Solving the generalized discrete logarithm problem here means the determination of non-negative integers \((i,j,k,l)\) such that \(M=A^i B^j A^kB^l.\) It is easy to see that

\begin{equation*} A^i=\begin{pmatrix} 1 & i \\ 0 & 1 \end{pmatrix} \quad \text{and} \quad B^j=\begin{pmatrix} 1 & 0 \\ j & 1 \end{pmatrix}. \end{equation*}

Hence it follows that

\begin{equation*} A^iB^jA^kB^l= \begin{pmatrix} 1 & i \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ j & 1 \end{pmatrix} \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ l & 1 \end{pmatrix}. \end{equation*}

Putting together the above computations we obtain that

\begin{equation*} \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} = \begin{pmatrix} 1+ij+l((1+ij)k+i) & (1+ij)k+i \\ j+l(jk+1) & jk+1 \end{pmatrix}. \end{equation*}

The matrix equation can be written as a system of equations as follows

\begin{equation*} \begin{aligned} 1+ij+l((1+ij)k+i) &=m_{11}, \\ (1+ij)k+i &=m_{12}, \\ j+l(jk+1) &=m_{21}, \\ jk+1 &=m_{22}.\end{aligned} \end{equation*}

The Groebner basis of the ideal

\begin{equation*} \begin{aligned} I= \langle \ 1+ij+l((1+ij)k+i)&-m_{11}, \\ (1+ij)k+i&-m_{12}, \\ j+l(jk+1) &-m_{21}, \\ jk+1 &-m_{22} \ \rangle\end{aligned} \end{equation*}

over the rationals is given by

\begin{equation*} \begin{aligned} GB=[l-jim_{21}+jm_{11}&-m_{21},\\ k+im_{22}&-m_{12},\\ jim_{12}m_{21}+ji+jm_{11}m_{12}-m_{11}+m_{12}m_{21}&+1,\\ jim_{22}-jm_{12}+m_{22}&-1,\\ m_{11}m_{22}-m_{12}m_{21}&-1].\end{aligned} \end{equation*}

Hence we need to handle the system of equations

\begin{equation*} \begin{aligned} l-jim_{21}+jm_{11}-m_{21}&=0,\\ k+im_{22}-m_{12}&=0,\\ jim_{22}-jm_{12}+m_{22}-1&=0.\end{aligned} \end{equation*}

In practice it can be solved efficiently for \(i,j,k\) and \(l.\) Let us consider a concrete example. Over \(\mathbb{F}_7\) we take the matrices

\begin{equation*} M=\begin{pmatrix} 5 & 2 \\ 6 & 4 \end{pmatrix}, \quad A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. \end{equation*}

We get the system of equations given by

\begin{equation*} \begin{aligned} 1+ij+l((i+ij)k+i)&=5 \\ (i+ij)k+i&=2 \\ j+l(jk+1)&=6 \\ jk+1&=4.\end{aligned} \end{equation*}

A solution of the above system is \((i,j,k,l)=(0,5,2,2)\) that is we have

\begin{equation*} M=A^0B^5A^2B^2. \end{equation*}

A SageMath implementation (based on the code written by Krisztián Dsupin in his BSc Thesis) of the above computation is as follows.

Figure 7.1. Discrete logarithm with special generators

Subsection 7.2 General case in \(PSL(2,\mathbb{F}_p)\)

The above method can be extended to more general groups. Let \(C,D\) be order \(p,\) non-commuting elements of \(PSL(2,\mathbb{F}_p).\) Consider the group \(G=<C,D>.\) We show that the discrete logarithm problem can be reduced to the previous case, that is we can solve it in \(<A,B>\) instead of \(<C,D>.\) To do so we try to determine \(g \in G= PSL(2,\mathbb{F}_p)\) for which

\begin{equation*} C=g^{-1}A^sg \quad \text{and} \quad D=g^{-1}B^tg, \end{equation*}

where \(s,t<p\) are non-negative integers. Let

\begin{equation*} g=\begin{pmatrix} g_1 & g_2 \\ g_3 & g_4 \end{pmatrix}. \end{equation*}

To compute \(g_1,g_2,g_3\) and \(g_4\) we may use the system of linear equations \(gC=A^sg\) and \(gD=B^tg.\) Suppose that we have determined such a matrix \(g,\) than we have

\begin{equation*} \begin{aligned} M&=C^iD^jC^kD^l \\ &=(g^{-1}A^sg)^i(g^{-1}B^tg)^j(g^{-1}A^sg)^k(g^{-1}B^tg)^l \\ &=(g^{-1}A^{si}g)(g^{-1}B^{tj}g)(g^{-1}A^{sk}gk(g^{-1}B^{tl}g) \\ &=g^{-1}A^{si}B^{tj}A^{sk}B^{tl}g.\end{aligned} \end{equation*}

Therefore we need to solve the discrete logarithm problem

\begin{equation*} M_1=A^xB^yA^vB^w , \end{equation*}

where \(M_1=gMg^{-1}\) and \(x=si, y=tj,v=sk,w=tl.\) Thus the problem is reduced and we can apply the method introduced previously. Let us describe a concrete example. Consider the matrices given by

\begin{equation*} M=\begin{pmatrix} 3 & 5 \\ 2 & 6 \end{pmatrix}, \quad C=\begin{pmatrix} 5 & 1 \\ 5 & 4 \end{pmatrix}, \quad D=\begin{pmatrix} 2 & 5 \\ 4 & 0 \end{pmatrix}. \end{equation*}

First we need to find an appropriate matrix \(g\) such that

\begin{equation*} \begin{aligned} \begin{pmatrix} g_1 & g_2 \\ g_3 & g_4 \end{pmatrix} \begin{pmatrix} 5 & 1 \\ 5 & 4 \end{pmatrix} &= \begin{pmatrix} 1 & s \\ 0 & 1 \end{pmatrix} \begin{pmatrix} g_1 & g_2 \\ g_3 & g_4 \end{pmatrix} \\ \begin{pmatrix} g_1 & g_2 \\ g_3 & g_4 \end{pmatrix} \begin{pmatrix} 2 & 5 \\ 4 & 0 \end{pmatrix} &= \begin{pmatrix} 1 & 0 \\ t & 1 \end{pmatrix} \begin{pmatrix} g_1 & g_2 \\ g_3 & g_4 \end{pmatrix}.\end{aligned} \end{equation*}

The above matrix equations yield the system of equations

\begin{equation*} \begin{aligned} g_1+4g_2&=0 \\ 5g_1-g_2&=0 \\ -g_1t+g_3-g_4&=0 \\ -g_2t+5g_3-g_4&=0 \\ -g_3s+4g_1+g_2&=0 \\ -g_4s+4g_1+3g_2&=0 \\ 4g_3+5g_4&=0 \\ g_3+3g_4&=0. \end{aligned} \end{equation*}

By means of Groebner basis technique it simplifies as follows

\begin{equation*} \begin{aligned} g_4s+g_2&=0 \\ g_2t+2g_4&=0 \\ g_1+4g_2&=0 \\ g_3+3g_4&=0.\end{aligned} \end{equation*}

We obtain that

\begin{equation*} g \cdot C - A^s \cdot g=\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} \quad \text{and} \quad g \cdot D - B^t \cdot g=\begin{pmatrix} 0 & 0 \\ \frac{4g_2st-g_2}{s} & \frac{-g_2st+g_2}{s} \end{pmatrix}. \end{equation*}

It follows easily that

\begin{equation*} (s,t) \in \{(1,2),(6,5),(3,3),(5,6),(4,4),(2,1)\}. \end{equation*}

If \(s=1\) and \(t=2,\) then we have \(g=\begin{pmatrix} 6 & 2 \\ 6 & 5 \end{pmatrix}\) and \(M_1=g \cdot M \cdot g^{-1}= \begin{pmatrix} 3 & 3 \\ 1 & 6 \end{pmatrix}.\) It remains to solve the discrete logarithm problem given by \(M_1=A^xB^yA^vB^w,\) where

\begin{equation*} A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. \end{equation*}

The approach we provided earlier gives

\begin{equation*} (x,y,v,w) \in \{(0,4,3,3),(1,3,4,2),(2,1,5,0),(3,2,6,1),(5,5,1,4),(6,6,2,5)\}. \end{equation*}

Thus the complete set of solutions of the original discrete logarithm problem \(M = C^iD^jC^kD^l\) is given by

\begin{equation*} (i,j,k,l) \in \{(0,2,3,5),(1,5,4,1),(2,4,5,0),(3,1,6,4),(5,6,1,2),(6,3,2,6)\}. \end{equation*}

SageMath summary.

groebner_basis(): Returns the Groebner basis of an ideal.
ideal(): Returns an ideal generated by polynomials in a ring.
multiplicative_order(): Returns the multiplicative order of an element.
solve_mod(): Solves certain equations/systems of equations modulo an integer.

Exercises 7.3 Exercises

1.

Let

\begin{equation*} A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \end{equation*}

be matrices over \(\mathbb{F}_{13}.\) Determine all solutions of the discrete logarithm problem

\begin{equation*} A^iB^jA^kB^l=\begin{pmatrix} 0 & 1 \\ 12 & 4 \end{pmatrix}. \end{equation*}

2.

Let

\begin{equation*} C=\begin{pmatrix} 9 & 3 \\ 7 & 10 \end{pmatrix}, \quad D=\begin{pmatrix} 0 & 12 \\ 7 & 2 \end{pmatrix} \end{equation*}

be matrices over \(\mathbb{F}_{17}.\) Determine all solutions of the discrete logarithm problem

\begin{equation*} C^iD^jC^kD^l=\begin{pmatrix} 14 & 12 \\ 3 & 16 \end{pmatrix}. \end{equation*}