capbtabboxtable[][]

# Complexity of Conjugacy Search in
some Polycyclic and Matrix Groups††thanks: This research is supported by
armasuisse Science and Technology.

Simran Tinani  Institute of Mathematics, University of Zurich,
Winterthurerstrasse 190, 8057 Zurich Carlo Matteotti  Eidgenössisches
Departement VBS, Papiermühlestrasse 20, 3003 Bern  Joachim Rosenthal
Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057
Zurich

###### Abstract

The most prominent algorithmic problem employed in the recently emerging field
of nonabelian group-based cryptography is the Conjugacy Search Problem (CSP).
While several methods of attacks on nonabelian protocols have been devised,
many of these are heuristic, protocol-specific, and focus on retrieving the
shared keys without solving the underlying CSP in the group. So far, the true
complexity of the CSP in different platform groups has not been sufficiently
investigated. In this paper, we study the complexity of various versions of
the CSP in polycyclic groups and matrix groups over finite fields. In
particular we show that in $\operatorname{GL}_{n}({\mathbb{F}_{q}})$ and in
polycyclic groups with two generators, a CSP where conjugators are restricted
to a cyclic subgroup is reducible to a set of $\mathcal{O}(n^{2})$ DLPs. As a
consequence of our results we also demonstrate the cryptanalysis of a few
independently proposed cryptosystems.

##  1 Introduction

The construction and realization of cryptographic systems that resist quantum
attacks presently constitutes an important area of research. Apart from
lattice-based, multivariate, and code-based cryptography, it has been proposed
recently to use the rich structure of nonabelian groups to construct quantum-
secure protocols for public key exchange, message encryption, and
authentication. Some recent surveys on this emerging field, called group-based
cryptography, can be found in [22] and [5].

The most prominent algorithmic problem employed for constructing nonabelian
protocols is the Conjugacy Search Problem (henceforth written CSP). While the
Discrete Logarithm Problem (henceforth written DLP) in a group $G$ requires
the recovery of the exponent $n$ when given the group elements $g$ and
$h=g^{n}$, the CSP requires the recovery of a conjugator $x\in G$, given the
elements $g$ and $h=x^{-1}gx$. To reflect this analogy, it is common to use
the notation $g^{x}:=x^{-1}gx$ for $g,x\in G$, which we also adopt in this
paper. If the conjugator is restricted to lie in a subgroup $A\subseteq G$, we
refer to the problem as an $A$-restricted CSP. In this paper we are
specifically interested in the case where $A$ is cyclic. We remark that
conjugation is an action of a group on itself, and thus all CSP-based
protocols may be seen as special cases of the semigroup action-based framework
introduced in [17].

The first and most prominently known protocols constructed based on the CSP
were by Anshel, Anshel and Goldfeld (AAG) [1], and Ko-Lee [15], both of whose
underlying problems is a specific restricted CSP. The authors of both these
systems proposed as platforms the Braid groups $B_{N}$. However, a number of
attacks [10], [21], [26] show that the braid groups are not suitable
platforms. Nevertheless, the possibility of finding another potential
nonabelian platform group for CSP-based protocols is still open to research.
Some other groups that have been proposed for use are polycyclic groups,
metabelian groups, $p$-groups, Thompson groups, and matrix groups.

When the underlying platform group is linear (i.e. embeds faithfully into a
matrix group over a field), several polynomial time attacks exist, which focus
on retrieving the private shared key without solving the CSP [16], [20], [26],
[2]. However, in general the computation of an efficient linear representation
may pose a serious roadblock for an adversary. Further, many of these attacks
are impractical to implement for standard parameter values. Such attacks are
also typically protocol-specific, and this always leaves open the possibility
of constructing a different protocol, again based on the CSP, where the known
attacks are avoided. So far, the true difficulty of the CSP in different
platforms has not been sufficiently investigated.

In this paper, we study the complexity of various versions of the CSP in two
well-known classes of linear groups: polycyclic groups and matrix groups over
finite fields. Polycyclic groups were suggested for cryptographic use in [4],
where some evidence was provided for resistance to some known attacks. Matrix
groups are important for any nonabelian system, since whenever the platform
group is linear, an efficient faithful representation reduces the underlying
problem to one in a matrix group. Several proposed nonabelian cryptosystems
use platforms that are special instances of polycyclic or matrix groups, and
employ problems either equivalent to, or easier than, the versions of the CSP
discussed in this paper.

Our results show that security of the independent systems in [9], [25], and
[28] relies on a problem at most as hard as set of DLPs, so that the CSP here
offers no novel security feature. More generally, a direct consequence of our
results is that a CSP-based protocol in a linear platform with efficient
representation must ensure that the conjugators come from a subgroup with more
than two generators in order to have any potential security benefit. On the
other hand, the case of finite polycyclic groups with two generators shows
that a larger subgroup $A$ often offers an attacker with more flexibility,
rendering the $A$-restricted CSP easier. We believe that our findings are
likely to allow for several other heuristic attacks in the general case, when
the conjugators are not carefully chosen. The algebraic reductions
demonstrated in this paper may also prove useful in future cryptanalysis
techniques for nonabelian protocols over different platform groups.

The paper is organized as follows. Section 2 deals with polycyclic groups,
given by their generators and relations. In Section 2.1 we give a brief
overview on polycyclic groups, and in Section 2.2 we discuss algorithms and
complexities for the group operations. In Section 2.3 we show that in the case
with two generators, there is a polynomial time solution for the CSP, and that
the $A$-restricted CSP, for a suitable choice of a cyclic subgroup $A$, is
equivalent to a DLP. We also show some reductions for polycyclic groups with
$3$ generators, and for the general $n$ generator case where $n-1$ generators
commute. We demonstrate two examples, also showing an extension of the method
to solving decomposition problems, thereby cryptanalysing the system in [25].
Finally, in Section 2.6 we discuss the consequences if a matrix representation
is used in place of the standard polycyclic presentation. Section 3 deals with
matrix groups. In Section 3.1 we provide a reduction of the $\langle
Z\rangle$-restricted CSP in $\operatorname{GL}_{n}({\mathbb{F}_{q}})$ to
$\mathcal{O}(n^{2})$ DLPs, dealing separately with the cases where $Z$ is
diagonalizable and not. In Section 3.2 we show how this result leads to a
cryptanalysis of the two systems proposed in [9] and [28].

##  2 Polycyclic groups

In [4], polycyclic groups were suggested as a potential platform for
conjugacy-based cryptography, and some evidence was provided for these groups
resisting the length-based attacks afflicting braid group-based systems. A
survey of polycyclic group-based cryptography can be found in [8]. This
section discusses the complexity of some special cases of the CSP in
polycyclic groups. We start by introducing polycyclic groups and some of their
basic properties, and in particular briefly discuss the complexity of
performing the group operations.

###  2.1 Background

######  Definition 1 (Polycyclic Group).

A polycyclic group is a group $G$ with a subnormal series
$G=G_{1}>G_{2}>\ldots>G_{n+1}=1$ in which every quotient $G_{i}/G_{i+1}$ is
cyclic. This series is called a polycyclic series.

######  Definition 2 (Power-Conjugate Presentation).

Let $G$ be a group with generators $a_{1},a_{2},\ldots,a_{n}$. Let
$I\subseteq\\{1,2,\ldots,n\\}$ denote a list of indices and $m_{i}>1$ be
integers corresponding to elements $i\in I$. A power-conjugate presentation is
a group presentation of the form

$\displaystyle G=\langle a_{1},a_{2},\ldots,a_{n}\mid$ $\displaystyle
a_{i}^{m_{i}}=w_{ii},\ i\in I,$ $\displaystyle a_{j}^{a_{i}}=w_{ij},\ 1\leq
i<j\leq n,$ $\displaystyle a_{j}^{a_{i}^{-1}}=w_{-ij},\ 1\leq i<j\leq
n,i\not\in I\rangle,$ (1)

where the words $w_{ij}$ are of the form
$w_{ij}=a_{\mid{i}\mid+1}^{l(i,j,\mid{i}\mid+1)}\ldots a_{n}^{l(i,j,n)}$, with
$l(i,j,k)\in\mathbb{Z}$, and $0\leq l(i,j,k)<m_{k}$ if $k\in I$.

######  Lemma 1 ([11]).

$G$ is polycyclic if and only if it has a polycyclic presentation.

Define $G_{i}=\langle a_{i},a_{i+1}\ldots a_{n}\rangle$, $1\leq i<n$,
$G_{n+1}=\langle 1\rangle$. The presentation in (2) is called _consistent_ if
$\lvert G_{i}/G_{i+1}\rvert=m_{i}$ whenever $i\in I$, and the $G_{i}/G_{i+1}$
is infinite whenever $i\not\in I$.

######  Definition 3 (Geodesic Form).

Let $G$ be generated by a set of alphabets $X$, and $a_{i}\in X\cup X^{-1}$,
$1\leq i\leq n$. A word $w=a_{1}a_{2}\ldots a_{n}$ is said to be in geodesic
from if there is no shorter word that represents the same group element as
$w$.

######  Definition 4 (Normal Form).

Given a consistent polycyclic presentation (2) for a group $G$, every element
$a$ of $G$ can be represented uniquely in the form
$a=a_{1}^{e_{1}}a_{2}^{e_{2}}\ldots a_{n}^{e_{n}}$ where $e_{i}\in\mathbb{Z}$,
$0\leq e_{i}\leq m_{i}$ for $i\in I$. This is called the normal form of $a$.

Henceforth, as is standard, we will use the normal form to represent words in
polycyclic groups, and also assume that the presentations we deal with are all
consistent. Given a word $w$ in $G$, the process by which minimal non-normal
subwords are reduced to normal form using the relations in (2) is called
_collection_.

Many different strategies for this process have been suggested, but the best-
known performance in most cases is achieved by the Collection from the Left
Algorithm [29], and its improvement in [7]. Under this, a word
$w=(x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\ldots
x_{n}^{\alpha_{n}})(x_{i_{1}}^{\beta_{1}}\ldots\ldots x_{i_{t}}^{\beta_{t}})$
is represented in two parts: collected part (as a vector
$(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})$) and uncollected stack of
generator powers $s=(x_{i_{1}}^{\beta_{1}},\ldots,x_{i_{t}}^{\beta_{t}})$. To
collect $w$ into normal form, a finite number of generator powers from the
uncollected part are iteratively pushed onto the collected part.

In general, the running time of this algorithm depends on the exponents
appearing across the whole process. Due to the dependence on the exponents in
the intermediate steps, the complexity remains a rough and unclear estimate.
It is clear that collection is a key part of the group operations since it is
involved in both multiplication and inversion of words in $G$, and so in
general operations in a polycyclic group may not be efficient. However, in
many special cases, the complexity can be bounded. We discuss the complexity
of computing in polycyclic groups for some cases, including all finite
polycyclic groups, in the next subsection.

###  2.2 Complexity of Group Operations

Throughout this section, $G$ denotes a polycylic group given by the
presentation $\eqref{pcpres}$. Below, we begin our discussion by showing that
collected words in the last two generators can be multiplied, inverted and
exponentiated, using fixed formulas. For simplicity, write the relations in
$x_{n-1}$ and $x_{n}$ as
$x_{n}^{x_{n-1}}=x_{n}^{L},x_{n}^{{x_{n-1}}^{-1}}=x_{n}^{D}$ for fixed
$L,D\in\mathbb{Z}$.

######  Lemma 2.

We have a formula to collect any word of the form $x_{n}^{i}x_{n-1}^{j}$. For
any $A,B\in\mathbb{Z}$,

$x_{n}^{B}x_{n-1}^{A}=\begin{cases}x_{n-1}^{A}{x_{n}}^{BL^{A}}\ \text{if }\
A\geq 0\\\ x_{n-1}^{A}{x_{n}}^{BD^{-A}}\ \text{if }\ A<0\end{cases}$ (2)

The following formula allows the computation of the product of $r$ words given
in normal form. It is easily verified by induction on $r$.

######  Lemma 3.

Let $r\geq 1$ and $w_{i}=x_{n-1}^{A_{i}}x_{n}^{B_{i}}$ for $1\leq i\leq r$,
and $w=w_{1}w_{2}\ldots w_{r}$. Define

$k_{j}=\begin{cases}1,A_{j}\geq 0\\\ 0,A_{j}<0,\end{cases},\
A_{i}^{+}=\sum\limits_{j=i+1}^{r}A_{j}k_{j},\
A_{i}^{-}=\sum\limits_{j=i+1}^{r}A_{j}(1-k_{j}).$

Then, $w=x_{n-1}^{A}x_{n}^{B}$, with $A=\sum\limits_{i=1}^{r}A_{i}$, and
$B=\sum\limits_{i=1}^{r}B_{i}L^{A_{i}^{+}}D^{A_{i}^{-}}$

######  Lemma 4.

Let $K>0$ and consider an element $w=x_{n-1}^{A}x_{n}^{B}$. Write $E(A)=L$, if
$A\geq 0$, $E=D$ if $A<0$, $F(A)=L$, if $A<0$, $F(A)=D$ if $A\geq 0$
($E_{j}=k_{j}L+(1-k_{j})D$). Then
$(x_{n-1}^{A}x_{n}^{B})^{K}=x_{n-1}^{KA}x_{n}^{B\left(\frac{E^{\lvert
KA\rvert}-1}{E^{\lvert A\rvert}-1}\right)}$, and
$(x_{n-1}^{A}x_{n}^{B})^{-K}=x_{n-1}^{-KA}x_{n}^{-BF^{\lvert
KA\rvert}\left(\frac{E^{\lvert KA\rvert}-1}{E^{\lvert A\rvert}-1}\right)}$.

Thus, operations on normal words in $x_{n-1}$ and $x_{n}$ have complexity
$\mathcal{O}(1)$. We now consider words in the three generators
$x_{n-2},x_{n-1},x_{n}$.

Define constants $A_{j}^{(k)},B_{j}^{(k)}$ with
$x_{n-2}^{-k}x_{j}x_{n-2}^{k}=x_{n-1}^{A_{j}^{(k)}}x_{n}^{B_{j}^{(k)}}$ for
$j=n-1,n$, and $k\in\mathbb{Z}$. Clearly, $A_{j}^{(\pm 1)}$ and $B_{j}^{(\pm
1)}$ can be read from the group presentation.

Given $A=A_{j}^{(k)}$ and $B=B_{j}^{(k)}$ for any $k\geq 0$, we obtain
$A_{j}^{(k+1)}$ and $B_{j}^{(k+1)}$ (resp. $A_{j}^{(k-1)}$ and $B_{j}^{(k-1)}$
if $k<0$) in time $\mathcal{O}(1)$ by computing
$x_{n-2}^{-1}(x_{n-1}^{A}x_{n}^{B})x_{n-2}=(x_{n-1}^{x_{n}})^{A}(x_{3}^{x_{1}})^{B}=w_{1}^{A}w_{2}^{B}$
which requires two substitutions from the presentation, two exponentiations
and one word multiplication, of words in $x_{n-1}$ and $x_{n}$. The square and
multiply method can be used for subsequent exponents, giving a total
complexity of $\mathcal{O}(\log k)$ for computing $(A_{j}^{(k)},B_{j}^{(k)})$.
Note that if $n\geq 4$ the complexity of computing
$x_{n-3}^{-1}(x_{n-2}^{A}x_{n-1}^{B}x_{n}^{C})x_{n-3}$ depends on all of the
exponents $A,B,C$, and their intermediate values, and from this case onwards
nothing concrete can be said about the complexity in general.

Below, we consider the case where we have a general bound $N$ for the
exponents on each generator at each step of collection. For instance, if each
generator $a_{i}$ has finite order $m_{i}$, the exponents on $a_{i}$ can
always be reduced in polynomial time, so we can assume without loss of
generality that $N=\max(m_{i})$. In particular this holds for all finite
polycyclic groups.

######  Proposition 1.

Let $n\geq 4$. For $j\leq n-3$, the complexity of multiplying two words, and
of inverting a single word, in the generators $x_{j}$, $x_{j+1},\ldots,x_{n}$
is $\mathcal{O}(\frac{(n-j)!}{2}(\log N)^{2(n-j-2)+1})$.

###### Proof.

Note that from the above discussion we have a complexity of $\mathcal{O}(\log
N)$ for multiplication and inversion of words in $x_{n-2}$, $x_{n-1}$ and
$x_{n}$. For $j\leq n-3$ we have

$\displaystyle
x_{j}^{-1}\;(x_{j+1}^{A_{j+1}}\;x_{j+2}^{A_{j+2}}\;\ldots\;x_{n}^{A_{n}})x_{j}=$
$\displaystyle{(x_{j+1}^{x_{j}})}^{A_{j+1}}\;{(x_{j+2}^{x_{j}})}^{A_{j+2}}\;\ldots\;{(x_{j+1}^{x_{j}})}^{A_{n}}$
$\displaystyle=$ $\displaystyle
w_{j+1,j}^{A_{j+1}}\;w_{j+2,j}^{A_{j+2}}\;\ldots\;w_{n,j}^{A_{n}}$
$\displaystyle=$
$\displaystyle\overline{w_{j+1,j}}\;\overline{w_{j+2,j}}\;\ldots\;\overline{w_{n,j}}$
$\displaystyle=$ $\displaystyle w$

where the expression in the second line is obtained through $(n-j)$
substitutions from the presentation, the expression in the third line is
computed in $\sum_{i=j+1}^{n}O(\log A_{i})$ word multiplications in
$x_{j+1},\ldots,x_{n}$, and the final value $w$ is computed in $(n-j)$ word
multiplications in $x_{j+1},\ldots,x_{n}$. So,
$x_{j}^{-1}(x_{j+1}^{A_{j+1}}x_{j+2}^{A_{j+2}}\ldots x_{n}^{A_{n}})x_{j}$ can
be computed in $\mathcal{O}((n-j)\log N)$ word multiplications in
$x_{j+1},\ldots,x_{n}$, and so
$x_{j}^{-K}(x_{j+1}^{A_{j+1}}x_{j+2}^{A_{j+2}}\ldots x_{n}^{A_{n}})x_{j}^{K}$
can be computed in $\mathcal{O}((n-j)\log K\log N)$ word multiplications in
$x_{j+1},\ldots,x_{n}$. Thus, two normal words in $x_{j}$,
$x_{j+1},\ldots,x_{n}$ can be multiplied by plugging in the value of the
conjugation by a power of $x_{j}$ and then performing a multiplication of two
words in $x_{j+1},\ldots,x_{n}$. So, the total complexity is
$\mathcal{O}((n-j)(\log N)^{2})$ word multiplications in
$x_{j+1},\ldots,x_{n}$. The result on multiplication then easily follows by
backwards induction on $j\leq n-3$. Similarly, a normal word in $x_{j}$,
$x_{j+1},\ldots,x_{n}$ can be inverted by performing an inversion of a word in
$x_{j+1},\ldots,x_{n}$ and then plugging in the value of the conjugation by a
power of $x_{j}$. So, one must perform $\mathcal{O}((n-j)(\log N)^{2})$ word
multiplications in $x_{j+1},\ldots,x_{n}$ and one inversion of a word in
$x_{j+1},\ldots,x_{n}$. It may be easily verified that this inversion too has
an overall complexity of $\mathcal{O}(\frac{(n-j)!}{2}(\log N)^{2(n-j-2)+1})$.
∎

###  2.3 CSP in a Polycyclic Group with two generators

We consider the case $n=2$, with two generators $x_{1}$ and $x_{2}$.
Throughout, we will write $N_{1}=\operatorname{ord}(x_{1})$ and
$N_{2}=\operatorname{ord}(x_{2})$ as the respective orders of $x_{1}$ and
$x_{2}$ in $G$, which are both allowed to be infinite. We have two relations
$x_{1}^{-1}x_{2}x_{1}=x_{2}^{L}$ and $x_{1}x_{2}x_{1}^{-1}=x_{2}^{D}$ (the
second is redundant if and only if $N_{1}$ is finite, in which case
$D=L^{N_{1}-1}$). Note that if $N_{2}$ is finite then $\gcd(L,N_{2})=1$, since
if not, writing $L_{2}=\gcd(L,N_{2})\neq 1$, we have
$x_{1}^{-1}x_{2}^{N_{2}/L_{2}}x_{1}=1$, or $x_{2}^{N_{2}/L_{2}}=1$, a
contradiction.

The following lemma is a consequence of Lemma 2 for the solution of the CSP.

######  Lemma 5.

The conjugated word
$(x_{1}^{c}x_{2}^{d})^{-1}(x_{1}^{a}x_{2}^{b})(x_{1}^{c}x_{2}^{d})$ can be
collected to $x_{1}^{g}x_{2}^{h}$ with $g=a$ and

$h=\begin{cases}-dL^{a}+bL^{c}+d;\ \text{if}\ c,\ a\geq 0\\\
-dL^{a}+bD^{-c}+d;\ \text{if}\ c<0,\ a\geq 0\\\ -dD^{-a}+bL^{c}+d;\ \text{if}\
c\geq 0,\ a<0\\\ -dD^{-a}+bD^{-c}+d;\ \text{if}\ c,\ a<0\end{cases}$

######  Theorem 1.

If $N_{2}=\operatorname{ord}(x_{2})$ is finite, the CSP has a polynomial time
solution in $G_{2}$.

###### Proof.

Suppose we are given an instance of the CSP, i.e. an equation
$(x_{1}^{c}x_{2}^{d})^{-1}(x_{1}^{a}x_{2}^{b})(x_{1}^{c}x_{2}^{d})=x_{1}^{e}x_{2}^{f}$,
where we want to solve the for $c$ and $d$. Then, from Lemma 5,
$a=e\pmod{N_{1}}$ and the CSP is reduced to solving a modular equation for two
unknowns $c$ and $d$.

If $a\geq 0$, we have $f+d(L^{a}-1)=bL^{c}$, or $f+d(L^{a}-1)=bD^{-c}$.
Writing $b_{1}=\gcd(b,N_{2})$, we see that a solution for $L^{c}$ (resp
$D^{-c}$) exists if and only if $d(L^{a}-1)=-f\pmod{b_{1}}$. Writing
$a_{1}=\gcd(b_{1},L^{a}-1)$, a solution $d$ for $d(L^{a}-1)=-f\pmod{b_{1}}$
exists if and only if $a_{1}\mid f$. By construction, a solution $(c,d)$
exists, so both these conditions are satisfied. Further, a solution $d$ to
$d(L^{a}-1)=-f\pmod{b}_{1}$ is given by
$d=-(f/a_{1})((L_{a}-1)/a_{1})^{-1}\pmod{b_{1}/a_{1}}.$ Write
$d=-(f/a_{1})((L_{a}-1)/a_{1})^{-1}+Mb_{1}/a_{1}$ for some $M\in\mathbb{Z}$
which we may choose. Then,

$M(L^{a}-1)/a_{1}=(f+d(L^{a}-1))/b_{1}=\begin{cases}(b/b_{1})L^{c},\;c\geq
0\\\ (b/b_{1})D^{-c},\;c<0\end{cases}$

Writing $A=(b/b_{1})^{-1}((L^{a}-1))/a_{1}$ (clearly $\gcd(A,N_{2})=1$), we
may take $M=A^{-1}\pmod{N_{2}}$, so that a solution is given by $c=0$. Then
$d=(L^{a}-1/a_{1})^{-1}(-f+b)/a_{1})).$

Similarly, a solution can be obtained for the case $a<0$ when $N_{1}=\infty$.
Thus, in both cases, a solution of the CSP involves a fixed number of
applications of the Euclidean algorithm, and so has polynomial time
complexity. ∎

######  Theorem 2.

If $N_{2}=\operatorname{ord}(x_{2})$ is finite, the $\langle
x_{1}\rangle$-restricted CSP in $G_{2}$ reduces to a DLP. Further, the
elements can be chosen so that it is exactly equivalent to a DLP in
$(\mathbb{Z}/N_{2}\mathbb{Z})^{*}$.

###### Proof.

Here we have the exponents from Lemma 5, with $d=0$, so the CSP reduces to the
retrieval of the exponent $c$ where $f=bL^{c}\pmod{N_{2}}$. Here, for a
solution to exist, $b_{1}=\gcd(b,N_{2})$ divides $f$, and we have
$f/b_{1}=L^{c}\pmod{N_{2}/b_{1}}$, so the adversary must solve the DLP with
base $L$ $\pmod{N_{2}/b_{1}}$, for the exponent $c$. Choosing the base element
so that $b$ satisfies $\gcd(b,N_{2})=1$, the restricted CSP is exactly
equivalent to a DLP in $(\mathbb{Z}/N_{2}\mathbb{Z})^{*}$. ∎

######  Remark 1.

If $N_{2}=\infty$, then the CSP in $G_{2}$ reduces to an exponential
Diophantine integer equation $f=-dL^{a}+bL^{c}+d$. As far as the authors’
knowledge goes, there is no known standard technique for solving such
equations, and trial and error would perhaps be the best method (for a general
reference see [23]). For instance, the adversary may try different values of
$c$ until $f-bL^{c}$ is a multiple of $L^{a}-1$, and subsequently solve for
$d$. On the other hand, the $\langle x_{1}\rangle$-restricted CSP in this case
has an easy solution: the adversary solves $f=bL^{c}$ for $c$ simply by taking
the real number base-$L$ logarithm of $f/b\in\mathbb{Z}$.

###  2.4 CSPs in some other polycyclic groups

####  2.4.1 $\langle x_{1}\rangle$ -restricted CSP in a polycyclic group with
three generators

Here it will be convenient to write $s=x_{1}$, $t_{1}=x_{2}$, $t_{2}=x_{3}$ in
the group presentation (2). Also, write $S=\langle s\rangle$ and $T=\langle
t_{1},t_{2}\rangle$, $\theta=\operatorname{ord}(s)$,
$\theta_{1}=\operatorname{ord}(t_{1})$, $\theta_{2}=\operatorname{ord}(t_{2})$
as the respective orders in $G$. Then $T$ is a polycyclic group with two
generators, and so from Lemma 2 we have
$t_{2}^{B}t_{1}^{A}=t_{1}^{A}t_{2}^{BL^{A}},\ A,B\in\mathbb{Z}$. Further, $S$
acts on $T$ via $s^{-1}t_{1}s=t_{1}^{a_{1}^{(1)}}t_{2}^{a_{2}^{(1)}},\
s^{-1}t_{2}s=t_{1}^{a_{1}^{(2)}}t_{2}^{a_{2}^{(2)}}$ for fixed integers
$a_{i}^{(j)},\ i,j\in\\{1,2\\}$.

Representing an element $t_{1}^{A}t_{2}^{B}$ of $T$ as a tuple
$(A,B)\in\mathbb{Z}/\theta_{1}\mathbb{Z}\times\mathbb{Z}/\theta_{2}\mathbb{Z}$
and writing $(t_{1}^{A}t_{2}^{B})^{s^{i}}=t_{1}^{A_{i}}t_{2}^{B_{i}}$ we can
describe the action of $S$ as a recurrence relation given by
$(A_{0},B_{0})=(A,B)$,

$(A_{i+1},B_{i+1})=\left(a_{1}^{(1)}A_{i}+a_{1}^{(2)}B_{i}\pmod{\theta_{1}},\
a_{2}^{(1)}L^{A_{i}a_{1}^{(2)}}\frac{L^{A_{i}a_{1}^{(1)}}-1}{L^{a_{1}^{(1)}}-1}+a_{2}^{(2)}\frac{L^{B_{i}a_{1}^{(2)}}-1}{L^{a_{1}^{(2)}}-1}\pmod{\theta_{2}}\right)$

Note that $A_{i}$ is always given $\pmod{\theta_{1}}$ and $B_{i}$ is always
given $\pmod{\theta_{2}}$. While the computation of $A_{i+1}$ and $B_{i+1}$
involves a “coupling” between these values, the final values seen are always
reduced, since they are the exponents in a reduced form word expression.
Further, while the first component $A_{i+1}$ of the tuple $(A_{i+1},B_{i+1})$
is linear in $A_{i}$ and $B_{i}$, it is no longer linear in the previous terms
of the sequence, since $B_{i}$’s relationship to $A_{i-1}$ and $B_{i-1}$ is
non-linear. The general complexity of the $\langle s\rangle$-restricted DLP,
i.e. recovering $i$ modulo $\theta$ from $(A_{i},B_{i})$ is not clear.
However, note that when $a_{1}^{(2)}=0=a_{2}^{(1)}$, the problem reduces to a
DLP in $(\mathbb{Z}/\theta_{1}\mathbb{Z})^{*}$.

####  2.4.2 $\langle x_{1}\rangle$-restricted CSP in $n$ generators when
$\langle x_{2},\ldots,x_{n}\rangle$ is abelian

Here it will be convenient to write $s=x_{1}$,
$t_{1}=x_{2},\ldots,t_{n-1}=x_{n}$ in the group presentation (2). Also write
$S=\langle s\rangle$ and $T=\langle t_{1},\ldots,t_{n-1}\rangle$,
$\theta=\operatorname{ord}(s)$, $\theta_{i}=\operatorname{ord}(t_{i})$. Write
$t_{i}^{s}=t_{1}^{a_{1}^{(i)}}\ldots t_{n-1}^{a_{n}^{(i)}}$ for $1\leq i\leq
n$. Representing the elements of $T$ as column vectors $(r_{1}\ldots,r_{n-1})$
of the exponents $r_{i}$ of the $t_{i}$, we can describe the action of $s$ on
$T$ by the endomorphism

$\mathbb{Z}_{\theta_{1}}\times\mathbb{Z}_{\theta_{2}}\times\ldots\times\mathbb{Z}_{\theta_{n}}\rightarrow\mathbb{Z}_{\theta_{1}}\times\mathbb{Z}_{\theta_{2}}\times\ldots\times\mathbb{Z}_{\theta_{n}}$
$(r_{1},\ldots,r_{n})\rightarrow\begin{bmatrix}a_{1}^{(1)}&\ldots&a_{1}^{(n)}\\\
a_{2}^{(1)}&\ldots&a_{2}^{(n)}\\\ \vdots&\cdots&\vdots\\\
a_{m}^{(1)}&\ldots&a_{m}^{(m)}\\\ \end{bmatrix}\cdot\begin{bmatrix}r_{1}\\\
r_{2}\\\ \vdots\\\ r_{m}\end{bmatrix}.$

Note that since $a_{i}^{(j)}$ is always given modulo $\theta_{i}$ the entries
of each column in the above matrix (call it $M$) actually lie in separate
groups. However, we may obtain a well-defined matrix power $M^{N}$ by first
computing the power over the integers, and then reducing the $i^{th}$ column
modulo $o_{i}$. Then, the action of $s^{N}$ on $T$ is given by the
endomorphism described by the matrix $M^{N}$ and the $\langle
x_{1}\rangle$-CSP is simply the problem of recovering $N$ given $M^{N}$. Note
that this is in general not the same as a matrix DLP because the entries of
each column actually lie in separate groups. However, if
$\theta_{1}=\ldots=\theta_{m}$ and $M$ is invertible over
$\mathbb{Z}/\theta_{1}\mathbb{Z}$, we can obtain $N$ by solving the matrix DLP
in the subgroup $\langle M\rangle$ of the ring
$Mat(\mathbb{Z}/\theta_{1}\mathbb{Z})$.

###  2.5 Examples

####  2.5.1 Holomorphs of Squarefree Cyclic Groups

The holomorph of a group $H$ is defined as the natural semidirect product of
$H$ with its automorphism group $\operatorname{Aut}(H)$. Let
$\operatorname{Hol}(C_{p})=C_{p}\rtimes\operatorname{Aut}(C_{p})$ of a cyclic
group $C_{p}$ of prime order $p$, generated by $g$.
$\operatorname{Aut}(C_{p})\cong\mathbb{Z}_{p}^{\times}$ is cyclic so
$\operatorname{Hol}(C_{p})$ is a polycyclic group with two generators. The
action of $\mathbb{Z}_{p}^{\times}$ on $C_{p}$ is written as a conjugation:
$k^{-1}h^{i}k=h^{ik},\ k\in\mathbb{Z}_{p}^{\times},\ i\in\mathbb{Z}$.

Given conjugate elements $g_{1}=h^{l}{k_{1}}$, $g_{2}=h^{n}k_{2}$ in $G$,
suppose we want to find $g=h^{m}k$ such that $g^{-1}g_{1}g=g_{2}$. It is easy
to check that $(h^{m}k)^{-1}(h^{l}{k_{1}})(h^{m}k)=h^{W}(k^{-1}k_{1}k)$ with
$W=k((-m+l)+mk_{1}^{-1})$. Subsequently we get $h^{W}=h^{n}$ and
$(k^{-1}k_{1}k)=k_{2}$. The latter equation is trivial, so one only needs to
solve $n=k(({k_{1}}^{-1}-1)m+l)\pmod{p}$ for $m$ and $k$.

If $k_{1}\neq 1\pmod{p}$ then $k_{1}^{-1}-1\in\mathbb{Z}_{p}^{\times}$ and for
any $k$ we find $m=\frac{1}{{k_{1}}^{-1}-1}(\frac{n}{k}-l)$. If
$k_{1}=1\pmod{p}$ then $lk=n\pmod{p}$. If $l=0\pmod{p}$ then $n=0\pmod{p}$ and
both $m$ and $k$ take any value (here $g_{1}=g_{2}=1$). If $l\neq 0\pmod{p}$
then $k=l^{-1}n$ and $m$ takes any value.

We remark here that $\operatorname{Hol}(C_{p})$ embeds into the ring
$\operatorname{Mat}_{2}(\mathbb{F}_{p})$ of $2\times 2$ matrices over
$\mathbb{F}_{p}$, so the above solution has an equivalent matrix formulation.
This solution may also easily be generalized to abelian groups of squarefree
order, for which there is a direct decomposition into cyclic factors,
computable in polynomial time [3].

####  2.5.2 Generalized Quaternions

A generalized quaternion group is a finite polycyclic group given by the
presentation

$Q_{2^{n}}=\langle x,y\mid x^{N}=1,y^{2}=x^{N/2},yx=x^{-1}y,N=2^{n-1}\rangle.$
(3)

Clearly, any element in this group has a normal form $x^{i}y^{j}$, where
$0\leq i\leq N$, $0\leq j\leq 1$.

One easily derives the relation ${y^{j}}{x^{i}}=x^{i(-1)^{j}}y^{j}$ for all
$i,j\in\mathbb{Z}$. Suppose we have a CSP instance
$(x^{i}y)^{-1}(x^{a}y)(x^{i}y)=x^{A}y$ and want to solve for $i$. We have,
$(y^{-1}x^{-i})(x^{a}y)(x^{i}y)=y^{-1}x^{a-2i}y^{2}=x^{2i-a}y$. Thus, the
exponent $i$ is found by solving $2i-a=A\pmod{N}$. Note that
$(x^{i}y)^{-1}(x^{a})(x^{i}y)=y^{-1}x^{a}y=x^{-a}$, so in this case any value
of $i$ is a valid solution. Similarly, since $x$ lies in the center of
$Q_{2^{n}}$, the $\langle x\rangle$-restricted CSP is trivial.

##### Decomposition in $Q_{2^{n}}$

It is easy to check that in $Q_{2^{n}}$ this collection method can be used to
solve other problems related to the CSP, like the decomposition problem of
[24]. In [25], the following protocol was proposed for key exchange in the
platform $Q_{2^{n}}$. The underlying problem is a variation of the
decomposition problem of [24]. As shown below, this protocol is easily broken
by collection in $Q_{2^{n}}$ and solving linear equations $\pmod{N}$.

######  Protocol 1.

The public parameters are $G=Q_{2^{n}}$ given by (3) and subgroups
$A_{1},A_{2}\subseteq\langle x\rangle$.

  1. 1.

    1. (a)

Alice picks secret elements $a\in G$, $b_{1},b_{2}\in A_{1}$ and sends
$x_{1}=b_{1}ab_{2}$ to Bob.

    2. (b)

Bob picks secret elements $d_{i}\in A_{2}$ and sends $x_{2}=d_{1}x_{1}d_{2}$
to Alice.

    3. (c)

Alice sends $x_{3}=b_{1}^{-1}x_{2}b_{2}^{-1}(=d_{1}ad_{2})$ to Bob.

  2. 2.

    1. (a)

Bob picks a secret element $c\in G$ and sends $y_{1}=d_{1}cd_{2}$ to Alice.

    2. (b)

Alice sends $y_{2}=b_{1}y_{1}b_{2}$ to Bob.

    3. (c)

Bob sends $y_{3}=b_{1}cb_{2}(=d_{1}^{-1}y_{2}d_{2}^{-1})$ to Alice.

The shared secret is
$b=ac=a(b_{1}^{-1}y_{3}b_{2}^{-1})=(d_{1}^{-1}x_{3}d_{2}^{-1})c$.

######  Proposition 2.

Protocol 1 can be broken in polynomial time by retrieving $a$ and $c$, which
reduces to a system of linear equations over $\mathbb{Z}_{N}$.

###### Proof.

We assume that $a\not\in\langle x\rangle$, since otherwise, finding $a$ is
trivial. Similarly, assume $c\not\in\langle x\rangle$. Write $a=x^{A}y$,
$c=x^{C}y$, $d_{i}=x^{D_{i}},\ b_{i}=x^{B_{i}},1\leq i\leq 2$. We have, by
collection,

$\displaystyle x_{1}=x^{n_{1}}y=x^{B_{1}+A-B_{2}}y,\quad
x_{2}=x^{n_{2}}y=x^{D_{1}+n_{1}-D_{2}}y,\quad
x_{3}=x^{n_{3}}y=x^{D_{1}+A-D_{2}}y,$ $\displaystyle
y_{1}=x^{m_{1}}y=x^{D_{1}+C-D_{2}}y,\quad
y_{2}=x^{m_{2}}y=x^{B_{1}+m_{1}-B_{2}}y,\quad
y_{3}=x^{m_{3}}y=x^{B_{1}+C-B_{2}}y$

The adversary sees the $x_{i}$’s and $y_{i}$’s, and thus also the $m_{i}$’s
and $n_{i}$’s, for $1\leq i\leq 3$, and needs to solve linear equations for
$A,C$, $D_{i}$’s, and $B_{i}$’s. The result is now clear. ∎

Observe that the discussion of this example is applicable in any group of the
form $\langle x\rangle\rtimes\langle y\rangle,y^{2}\in\langle x\rangle$.
Another notable example is the dihedral group $D_{2n}$.

###  2.6 Using matrix representations of polycyclic groups

Let $G$ be given by the presentation (2). It is known that every polycyclic
group is linear, and thus embeds faithfully into a matrix group over some
field. More precisely, there exists $m>0$, a field $\mathbb{F}$ and an
injective homomorphism $\phi:G\rightarrow\operatorname{GL}_{m}(\mathbb{F})$.

Suppose that this matrix representation is used by the designer of the
cryptosystem to hide the structure of $G$. The public parameters are the
generator matrices $M_{i}=\phi(a_{i})$ and a base matrix $M_{x}$, and
operations take place in $\operatorname{GL}_{m}(\mathbb{F})$. Let $M_{y}$
denote one of the conjugated public keys. Note that given the generator
matrices, an adversary can compute their orders in polynomial time using
binary search. However, to reconstruct the presentation of $G$ and reduce the
problem back to the CSP in $G$, they are faced with the following problem:
given a matrix $X\in\langle M_{1},\ldots,M_{n}\rangle$, find integers
$(i_{1},\ldots,i_{n})$ such that $X=M_{1}^{i_{1}}\ldots M_{n}^{i_{n}}$.
Clearly, by solving $\mathcal{O}(n^{2})$ instances of this problem they can
compute the presentation of $G$ and the words representing $M_{x}$ and
$M_{y}$, thereby reducing the problem back to the CSP in $G$.

This problem has been discussed in [14], and is called the Generalized
Discrete Logarithm Problem (GDLP). The thesis [12] discusses some square-root
type algorithms for the GDLP in finite matrix groups. The case $n=2$ has been
discussed for general finite groups in [19] and [13], both of which show a
square root algorithm to reduce the GDLP to at most two DLPs. Observe that in
$Q_{2^{n}}$, this process introduces a single matrix DLP into the protocol: an
adversary sees matrices $A=M_{x}^{i}M_{y}$ or $A=M_{x}^{i}$, and so can
recover $i$ by solving one of the matrix DLPs $AM_{y}^{-1}=M_{x}^{i},\
A=M_{x}^{i}$. Therefore, in general using the matrix representation likely
does not offer any novel security feature, though it may enhance the overall
security.

Now, suppose that the original problem is given as a CSP in $G$ and the
adversary is able to efficiently compute a faithful representation
$\phi:G\rightarrow\operatorname{GL}_{m}({\mathbb{F}_{q}})$ as well as its
inverse. Denote by $x\in G$ the public base element and $y=g^{-1}xg\in G$ the
public key. Then, it suffices for the adversary to find a matrix
$M_{g}\in\phi(G)$ such that $M_{g}^{-1}\phi(x)M_{g}=\phi(y)$, so solving a CSP
in $\phi(G)$ breaks the system. In fact, if the original CSP in $G$ is an
$A$-restricted CSP for $A\leq G$ cyclic, then it is not even necessary to
compute $\phi^{-1}$ since the secret here is essentially an integer. In
Theorem 1, we will see that an $A$-restricted CSP in
$\operatorname{GL}_{m}(\mathbb{F})$ is reducible to a set of
$\mathcal{O}(m^{2})$ DLPs over $\mathbb{F}$. So, any system with a linear
platform must ensure that the subgroup from which conjugators are chosen has
at least two generators. We remark here that in the case where such an
efficient representation $\phi$ and its inverse are available, several attacks
exist to directly retrieve the shared key, see [26], [16], [20], [2].

##  3 Matrix Groups

Throughout this section, $q$ denotes a power of a prime $p$ and
${\mathbb{F}_{q}}$ denotes the finite field with $q$ elements, and
$\operatorname{ord}(a)$ denotes the multiplicative order of an element
$a\in\mathbb{F}_{q}^{*}$.

Matrix groups over finite fields have served as platform groups for several
proposed protocols. In [18] and [6], the DLP over the matrix group
$\operatorname{GL}_{n}(\mathbb{F}_{q})$ was studied and shown to be no more
difficult than the DLP over a small extension of $\mathbb{F}_{q}$, and
consequently less efficient in terms of key sizes for the same security level.
Most known nonabelian platform groups are linear, i.e. they embed faithfully
into a matrix group. If this embedding and its inverse can efficiently be
computed by an adversary, the security of the system depends on that of the
matrix CSP rather than that in the original platform.

It is then natural and important to study the complexity of the CSP over
matrix groups. Several attacks exist to directly retrieve the shared key from
CSP-based protocols without computing the secret keys [26], [16], [20], [2].
However, to the best of our knowledge, the CSP and its variants have not been
investigated. In this section, we study the $A$-restricted matrix CSP for a
cyclic subgroup $A\subseteq\operatorname{GL}_{n}(\mathbb{F}_{q})$. Here, for
maximum generality we also allow the base element be a non-invertible matrix.
In other words, we provide a cryptanalysis of Protocol 2 over a ring $R$, for
the case $R=\operatorname{Mat}_{n}(\mathbb{F}_{q})$ of $n\times n$ matrices
over ${\mathbb{F}_{q}}$.

######  Protocol 2.

Let $X\in R$ and $Z\in R^{*}$ be public elements.

  1. 1.

Alice picks a secret integer $r\in\mathbb{Z}$ and publishes $Z^{-r}XZ^{r}$.

  2. 2.

Bob picks a secret integer $s\in\mathbb{Z}$ and publishes $Z^{-s}XZ^{s}$.

  3. 3.

The shared secret is $Z^{-s-r}XZ^{s+r}$.

In subsection 1, we provide a polynomial time reduction of recovering
$r\in\mathbb{Z}$ to a set of $\mathcal{O}(n^{2})$ DLPs. In subsection 2, we
show how this enables a full cryptanalysis of the system proposed in [28].

######  Remark 2.

Similarly to [6] (also mentioned in [18]) we will use an easy generalization
of the Chinese Remainder Theorem (CRT) for systems of equations of the form
$x\equiv x_{i}\pmod{\theta_{i}},1\leq i\leq s$, where the $\theta_{i}$ are not
necessarily coprime, but a solution is required
$\pmod{\theta}:=\operatorname{lcm}_{i}\theta_{i}$. Write
$\theta=p_{1}^{e_{1}}\ldots p_{t}^{e_{t}}$ as the prime factorization of
$\theta$. For each $j\in\\{1,\ldots,t\\}$, let
$\emptyset\neq\mathcal{I}_{j}\subseteq\\{1,\ldots,s\\}$ denote the list of
indices $i$ such that $p_{j}^{e_{j}}\mid\theta_{i}$. If a solution $x$ to the
original system of equations exists we have
$x_{i}-x_{i^{\prime}}=0\pmod{p_{j}^{e_{j}}}$ for each
$i,i^{\prime}\in\mathcal{I}_{J}$ and $x=x_{i_{0}}\pmod{p_{j}^{e_{j}}}$ for any
$i_{0}\in\mathcal{I}_{j}$. So if a solution exists, we can translate the
original system to one where the moduli are coprime, and so can be solved with
the CRT.

###  3.1 $\langle Z\rangle$-restricted CSP in
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$

Suppose that $Z^{-r}XZ^{r}=Y$, the adversary sees $X$, $Z$, and
$Y\in\operatorname{Mat}_{n}({\mathbb{F}_{q}})$, the integer $r$ is secret.
There exists an extension $\mathbb{F}_{q^{k}}$ and a unique matrix
$P\in\operatorname{GL}_{n}(\mathbb{F}_{q^{k}})$ (computable in polynomial
time, by Algorithm 1 in [18]) such that $J_{Z}=PZP^{-1}$, where $J_{Z}$ is the
Jordan Normal form of $Z$. Here $\mathbb{F}_{q^{k}}$ is the smallest extension
containing all eigenvalues of $Z$, and $k$ is polynomial in $q$ and $n$ [18].
Let $\theta_{Z}$ be the order of $Z$ in the group
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$ and $\theta_{J}$ be the order of
$J_{Z}$ in the group $\operatorname{GL}_{n}(\mathbb{F}_{q^{k}})$. Then,
clearly since $J_{Z}=PZP^{-1}$ we have $\theta_{Z}=\theta_{J}$. Further, we
only require a value of $r$ modulo $\theta_{Z}$ to break the system.

Consider $M=PXP^{-1}$ and $N=PYP^{-1}$. Note that these are both computable by
the adversary. It is easily verified that $Z^{-r}XZ^{r}=Y\iff
J_{Z}^{-r}MJ_{Z}^{r}=N.$ Thus, to recover $r$ we may assume that $Z$ is
already in Jordan form. We divide the rest of the analysis into two cases. We
first consider the case where $Z$ is diagonalizable.

####  3.1.1 Case: $J_{Z}$ is diagonal.

We write $M=(M_{i,j})_{n\times n}$ and $N=(N_{i,j})_{n\times n}$.

######  Theorem 3.

If $J_{Z}=\begin{pmatrix}d_{1}&\ldots&0\\\ \vdots&\ddots&\vdots\\\
0&\ldots&d_{n}\end{pmatrix}$ is diagonal then the retrieval of $r$ in Protocol
2 reduces to solving at most $n^{2}$ DLPs over $\mathbb{F}_{q^{k}}$.

###### Proof.

Note that $d_{i}\neq 0\ \forall\ i$ since $J_{Z}$ is invertible. We expand
$J_{Z}^{-r}MJ_{Z}^{r}=N$:

$\displaystyle\begin{pmatrix}d_{1}^{r}&\ldots&0\\\ \vdots&\ddots&\vdots\\\
0&\ldots&d_{n}^{r}\end{pmatrix}\begin{pmatrix}M_{11}&\ldots&M_{1n}\\\
\vdots&\ddots&\vdots\\\
M_{n1}&\ldots&M_{nn}\end{pmatrix}\begin{pmatrix}d_{1}^{-r}&\ldots&0\\\
\vdots&\ddots&\vdots\\\
0&\ldots&d_{n}^{-r}\end{pmatrix}=\begin{pmatrix}N_{11}&\ldots&N_{1n}\\\
\vdots&\ddots&\vdots\\\ N_{n1}&\ldots&N_{nn}\end{pmatrix}$ $\displaystyle\iff$
$\displaystyle M_{ij}(d_{i}d_{j}^{-1})^{r}=N_{ij},\ 1\leq i,j\leq n.$ (4)

By assumption $M$ and $N$ are nonzero matrices, so there exists at least one
pair of indices $(i,j)$ such that $M_{ij}\neq 0$, $N_{ij}\neq 0$. For any such
pair we have $(d_{i}d_{j}^{-1})^{r}=M_{ij}^{-1}N_{ij}$, so $r$
$\pmod{\operatorname{ord}(d_{i}d_{j}^{-1})}$ is found by solving a DLP in
$\mathbb{F}_{q^{k}}$. Repeating this for all such pairs $(i,j)$, we may
compute $r$ modulo ${\operatorname{lcm}\limits_{\exists(i,j)\mid M_{ij}\neq
0}(\operatorname{ord}(d_{i}^{-1}d_{j}))=\operatorname{lcm}\limits_{d_{i}\neq
0}(\operatorname{ord}(d_{i}))=\theta_{Z}}$ using the generalized Chinese
Remainder Theorem (see Remark 2). ∎

####  3.1.2 Case: $J_{Z}$ is not diagonal

Suppose that $\small J_{Z}=\begin{pmatrix}J_{1}&\ldots&0\\\
\vdots&\ddots&\vdots\\\ 0&\ldots&J_{s}\end{pmatrix}$ is the Jordan-Normal form
of $Z$, where each $\small J_{i}=\begin{pmatrix}\lambda_{i}&1&\ldots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\ldots&1\\\
0&0&\ldots&\lambda_{i}\end{pmatrix},\ 1\leq i\leq s$, is a $d_{i}\times d_{i}$
Jordan block corresponding to the eigenvalue
$\lambda_{i}\in\mathbb{F}_{q^{k}}$, and $d_{i}>1$ for at least one $i$.
Denoting $\binom{-n}{k}:=(-1)^{k}\binom{n+k-1}{k}$, and with the convention
$\binom{r}{m}=0$ if $m<r$ and $r>0$, we have by induction, for $r\geq 1$,

$\displaystyle\small
J_{i}^{r}=\begin{pmatrix}\lambda_{i}^{r}&\binom{r}{1}\lambda_{i}^{r-1}&\ldots&\binom{r}{d_{i}-1}\lambda_{i}^{r-d_{i}+1}\\\
0&\lambda_{i}^{r}&\ldots&\binom{r}{d_{i}-2}\lambda_{i}^{r-d_{i}+2}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\ldots&\binom{r}{1}\lambda_{i}^{r-1}\\\
0&0&\ldots&\lambda_{i}^{r}\end{pmatrix},\quad
J_{i}^{-r}=\begin{pmatrix}\lambda_{i}^{-r}&\binom{-r}{1}\lambda_{i}^{-r-1}&\ldots&\binom{-r}{d_{i}-1}\lambda_{i}^{-r-d_{i}+1}\\\
0&\lambda_{i}^{-r}&\ldots&\binom{-r}{d_{i}-2}\lambda_{i}^{-r-d_{i}+2}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\ldots&\binom{-r}{1}\lambda_{i}^{-r-1}\\\
0&0&\ldots&\lambda_{i}^{-r}\end{pmatrix}$

More concisely, for any $1\leq i\leq s$, $r\in\mathbb{Z}$,
$({J_{i}}^{r})_{(k,l)}=\binom{r}{l-k}\lambda_{i}^{r-l+k}$, $0\leq k,l\leq
d_{i}$. Now, we write $M$ and $N$ as block matrices with $s^{2}$ $d_{i}\times
d_{j}$ blocks $(M_{i,j})_{d_{i}\times d_{j}}$, $(N_{i,j})_{d_{i}\times
d_{j}}$:

$M=\begin{pmatrix}(M_{1,1})_{d_{1}\times d_{1}}&\ldots&(M_{1,s})_{d_{1}\times
d_{s}}\\\ \vdots&\ddots&\vdots\\\ (M_{s,1})_{d_{s}\times
d_{1}}&\ldots&(M_{s,s})_{d_{s}\times d_{s}}\end{pmatrix},\quad
N=\begin{pmatrix}(N_{1,1})_{d_{1}\times d_{1}}&\ldots&(N_{1,s})_{d_{1}\times
d_{s}}\\\ \vdots&\ddots&\vdots\\\ (N_{s,1})_{d_{s}\times
d_{1}}&\ldots&(N_{s,s})_{d_{s}\times d_{s}}\end{pmatrix}.$

The next result reduces the problem of recovering $r$ from Protocol 2 to a set
of $s^{2}$ matrix equations involving Jordan blocks.

######  Lemma 6.

$J_{Z}^{-r}MJ_{Z}^{r}=N\iff J_{i}^{-r}M_{i,j}J_{j}^{r}=(N_{i,j})_{d_{i}\times
d_{j}}$ $\forall\ 1\leq i,j\leq s$.

###### Proof.

The result is clear from the observation that $J_{Z}^{-r}MJ_{Z}^{r}=$

$\displaystyle\begin{pmatrix}J_{1}^{-r}&\ldots&0\\\ \vdots&\ddots&\vdots\\\
0&\ldots&J_{s}^{-r}\end{pmatrix}\begin{pmatrix}M_{11}&\ldots&M_{1s}\\\
\vdots&\ddots&\vdots\\\ M_{s,1}&\ldots&M_{s,s}\\\
\end{pmatrix}\begin{pmatrix}J_{1}^{r}&\ldots&0\\\ \vdots&\ddots&\vdots\\\
0&\ldots&J_{s}^{r}\end{pmatrix}=\begin{pmatrix}J_{1}^{-r}M_{11}J_{1}^{r}&\ldots&J_{1}^{-r}M_{1s}J_{s}^{r}\\\
\vdots&\ddots&\vdots\\\
J_{s}^{-r}M_{s1}J_{1}^{r}&\ldots&J_{s}^{-r}M_{ss}J_{s}^{r}\end{pmatrix}.$

∎

######  Lemma 7.

Writing $M_{i,j}=(m_{l,k}^{(i,j)})$, $N_{i,j}=(n_{l,k}^{(i,j)})$, we have
$J_{Z}^{-r}MJ_{Z}^{r}=N\iff$

$\small
n_{f,h}^{(i,j)}=\sum_{k=1}^{h}\sum_{l=f}^{d_{i}}\binom{-r}{l-f}\binom{r}{h-k}\
m_{l,k}^{(i,j)}\lambda_{i}^{-r+f-l}\lambda_{j}^{r-h+k}\ \forall 1\leq f\leq
d_{i},\ 1\leq h\leq d_{j},1\leq i,j\leq s.$

###### Proof.

Recall that $({J_{i}}^{r})_{(k,l)}=\binom{r}{l-k}\lambda_{i}^{r-l+k)}$ for any
integer $r$ and any $1\leq k,l\leq d_{i}$. We compute the $(f,h)$th term of
$J_{i}^{-r}M_{ij}J_{j}^{r}$. Note that for $1\leq g\leq d_{i}$ the $(f,g)$th
term of $J_{i}^{-r}M_{i,j}$ is given by
$\sum_{l=f}^{d_{i}}\binom{-r}{l-f}\lambda_{i}^{-r+f-l}m_{l,g}^{(i,j)}$. Thus,
the $(f,h)$th term of $N_{i,j}=J_{i}^{-r}M_{i,j}J_{j}^{r}$ is

$\displaystyle
n_{f,h}^{(i,j)}=\sum_{g=1}^{h}\sum_{l=f}^{d_{i}}\binom{-r}{l-f}\binom{r}{h-g}\
m_{l,g}^{(i,j)}\lambda_{i}^{-r+f-l}\lambda_{j}^{r-h+g}.$ (5)

For the equality $J_{i}^{-r}M_{ij}J_{j}^{r}=N_{ij}$ we require
$n_{f,h}^{(i,j)}=m_{f,h}^{(i,j)}$ for all indices $1\leq f,h\leq d_{i}$. The
result now follows from Lemma 6.∎

Now, by assumption, $M\neq 0$. So, we may choose the largest index
$l_{0}^{(i,j)}$ such that the $l_{0}^{(i,j)}$th row of $M_{i,j}$ has at least
one nonzero term. Let $g_{0}^{(i,j)}$ be the smallest column index such that
$m_{l_{0},g_{0}}^{(i,j)}\neq 0$. We have, $m_{l,g}^{(i,j)}=0\ \forall\
l>l_{0},1\leq g\leq d_{j}$, and $m_{l_{0},g}^{(i,j)}=0\ \forall\ g<g_{0}$.

Taking $f=l_{0},h=g_{0}+1$, by Equation (5) the $(f,h)^{th}$ term of
$N_{i,j}=J_{Z}^{-r}M_{i,j}J_{Z}^{r}$ is given by

$\displaystyle n_{l_{0},g_{0}+1}^{(i,j)}=$
$\displaystyle\sum_{g=1}^{g_{0}+1}\sum_{l=l_{0}}^{d_{i}}\binom{-r}{l-l_{0}}\binom{r}{g_{0}+1-g}\
m_{l,g}^{(i,j)}\lambda_{i}^{-r+l_{0}-l}\lambda_{j}^{r-g_{0}-1+g}$
$\displaystyle=\sum_{g=g_{0}}^{g_{0}+1}\binom{r}{g_{0}+1-g}m_{l_{0},g}^{(i,j)}\lambda_{i}^{-r}\lambda_{j}^{r-g_{0}-1-g}$
$\displaystyle=rm_{l_{0},g_{0}}^{(i,j)}\lambda_{j}(\lambda_{i}^{-1}\lambda_{j})^{r}+m_{l_{0},g_{0}+1}^{(i,j)}(\lambda_{i}^{-1}\lambda_{j})^{r}$
(6)

In particular, for $i=j$, we have the equation
$rm_{l_{0},g_{0}}^{(i,j)}\lambda_{j}^{-1}+m_{l_{0},g_{0}+1}^{(i,j)}=n_{l_{0},g_{0}+1}^{(i,j)}$,
where by construction, $m_{l_{0}g_{0}}^{(i,j)}\neq 0$. This can be solved to
get $r^{\prime}:=r\pmod{p}$. We thus have the following results.

######  Proposition 3.

The value of $r^{\prime}:=r\pmod{p}$ can be computed in polynomial time.

######  Proposition 4.

Computing $r\pmod{\underset{1\leq i\leq
s}{\operatorname{lcm}}\operatorname{ord}(\lambda_{i})}$ reduces in polynomial
time to solving at most $s^{2}$ DLPs in $\mathbb{F}_{q^{k}}$.

###### Proof.

We write $r=r^{\prime}+pw$ for $w\in\mathbb{Z}$. From equation (3.1.2), since
$m_{l_{0},g_{0}}^{(i,j)}\in\mathbb{F}_{q^{k}}$, we have

$m_{l_{0},g_{0}+1}^{(i,j)}=rm_{l_{0},g_{0}}^{(i,j)}\lambda_{j}(\lambda_{i}^{-1}\lambda_{j})^{r}+m_{l_{0},g_{0}+1}^{(i,j)}(\lambda_{i}^{-1}\lambda_{j})^{r}=(\lambda_{i}^{-1}\lambda_{j})^{r}(r^{\prime}m_{l_{0},g_{0}}^{(i,j)}\lambda_{j}+m_{l_{0},g_{0}+1}^{(i,j)}).$

Equating
$(\lambda_{i}^{-1}\lambda_{j})^{r}(r^{\prime}m_{l_{0},g_{0}}^{(i,j)}\lambda_{j}+m_{l_{0},g_{0}+1}^{(i,j)})=n_{l_{0},g_{0}+1}^{(i,j)}$
for $i\neq j$, we see that $r$ can now be recovered
$\pmod{\operatorname{ord}(\lambda_{i}^{-1}\lambda_{j})}$ by solving a DLP.
Repeating this process for all pairs $(i,j)$, and using the generalized CRT
(see Remark 2) we get $r$ modulo ${\underset{1\leq i<j\leq
s}{\operatorname{lcm}}\operatorname{ord}(\lambda_{i}^{-1}\lambda_{j})=\underset{1\leq
i\leq s}{\operatorname{lcm}}\operatorname{ord}(\lambda_{i})}$.∎

##### Computing $r\pmod{\theta_{Z}}$

As before, $\theta_{Z}$ denotes the order of $J_{Z}$ in the group
$GL(\mathbb{F}_{q^{k}})$. We will now show how Propositions 3 and 4 allow us
to compute $r\pmod{\theta_{Z}}$. We have the following result on the value of
$\theta_{Z}$ from [18].

######  Lemma 8 ([18]).

The order $\theta_{Z}$ of $J_{Z}$ is $\underset{1\leq i\leq
s}{\operatorname{lcm}}(\lambda_{i})\cdot p\\{t\\}$, where $t$ is the largest
Jordan block in $J_{Z}$ and $p\\{t\\}$ denotes the smallest power of p greater
than or equal to $t$.

Below, we show that if we can compute $r\pmod{p}$, then by extension we can
find $r\pmod{p\\{t\\}}$.

######  Lemma 9.

Suppose that an Algorithm A returns $r\pmod{p}$ for an equation of the form
$Z^{-r}XZ^{r}=Y$. Then, for any $v\geq 1$, one may find $r\pmod{p^{v}}$ with
$v$ applications of Algorithm A.

###### Proof.

We write $r=r_{0}+r_{1}p+\ldots+r_{v-1}p^{v-1}\pmod{p^{v}}$. With one
application of Algorithm A, one finds $r\pmod{p}=r_{0}$, and then compute
$Z_{1}=Z^{p},\ Y_{1}=Z^{r_{0}}YZ^{-r_{0}},\
r^{\prime}=r_{1}+r_{2}p+\ldots+r_{v-1}p^{v-2}$. Then, we have an equation
$Z_{1}^{-r^{\prime}}XZ_{1}^{r^{\prime}}=Y_{1}$. One now uses Algorithm A again
to find $r^{\prime}\pmod{p}=r_{1}$. In $v$ applications of Algorithm A, we
recover $r\pmod{p^{v}}$. ∎

Finally, we can prove the final result of this section.

######  Theorem 4.

Let $J_{Z}$ be non-diagonal, and composed of $s$ Jordan blocks. Then, the
computation of $r$ from Protocol 2 is polynomial time reducible to a set of
$s^{2}$ DLPs over $\mathbb{F}_{q^{k}}$.

###### Proof.

From Propositions 3 and 4, we may compute $r\pmod{\underset{1\leq i\leq
s}{\operatorname{lcm}}\lambda_{i}}$ and $r^{\prime}=r\pmod{p}$ with the same
time complexity as solving $s^{2}$ DLPs in ${\mathbb{F}_{q}}$. Note that since
the multiplicative order of any element of $\mathbb{F}_{q^{k}}^{\times}$
divides $q^{k}-1$, the values of $r^{\prime}=r\pmod{p}$ and
$r\pmod{\underset{1\leq i\leq
s}{\operatorname{lcm}}\operatorname{ord}(\lambda_{i})}$ are obtained
independently. Now, write $p\\{t\\}=p^{v}\leq q^{k}$, by Lemma 9, we can
obtain $r\pmod{p^{v}}$ from $r^{\prime}$ in polynomial time $\mathcal{O}(k\log
q)$. Combining $r\pmod{p^{v}}$ and $r\pmod{\underset{1\leq i\leq
s}{\operatorname{lcm}}\lambda_{i}}$ using the Chinese Remainder Theorem, we
get $r\pmod{\theta_{Z}}$, as required. It is also clear that every step apart
from the DLPs has polynomial time complexity. ∎

We may thus summarize the results of Theorems 3 and 4 as follows.

######  Corollary 1.

The $\langle Z\rangle$-restricted CSP in
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$ reduces in polynomial time to
$\mathcal{O}(n^{2})$ DLPs over a small extension $\mathbb{F}_{q^{k}}$ of
${\mathbb{F}_{q}}$.

######  Remark 3.

While we have only discussed the search variant of the conjugacy problem, it
is not hard to show that the arguments of this section also reduce the
decisional variant of the CSP to a set of corresponding decisional versions of
the DLP and generalized CRT. Further, this may be used, along with a
collision-type square-root algorithm, to solve any $A$-restricted CSP in
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$, where $A$ is abelian.

###  3.2 Applications to Cryptanalysis

####  3.2.1 Protocol based on Quaternions $\pmod{p}$

In [28], a protocol similar to Protocol 2 was proposed for the case of another
ring $R=H_{p}$, which we will refer to as the quaternions mod $p$. Recall that
the set of all Lipchitz quaternions is defined as
$L=\\{a=a_{1}+a_{2}i+a_{3}j+a_{4}k:a_{1},a_{2},a_{3},a_{4}\in\mathbb{Z}\\}.$
Similarly, the Hurwitz quaternions are given by
$H=\\{a=a_{1}+a_{2}i+a_{3}j+a_{4}k:a_{1},a_{2},a_{3},a_{4}\in\mathbb{Z}+\frac{1}{2}\mathbb{Z}\\}.$

For a prime $p$, the authors define $H_{p}$ as the set
$\\{a=a_{1}+a_{2}i+a_{3}j+a_{4}k\mid a_{i}\in\mathbb{Z}_{p}\\}$. Addition,
multiplication, the norm $||\cdot||$, and conjugates are defined in the usual
way as in quaternion algebras (for an exposition on arithmetic in quaternion
sets, see [27]), but over the base ring $\mathbb{Z}_{p}$. The quaternion $a$
is invertible in $H_{p}$ if and only if $||a||\neq 0\pmod{p}$.

Denote by $H_{p}^{*}$ the set of all invertible quaternions in $H_{p}$. The
protocol in [28] is described as follows:

######  Protocol 3.

  1. 1.

Alice and Bob agree to choose randomly public elements $x\in H_{p}$ $,z\in
H_{p}^{*}$.

  2. 2.

Alice picks two secret integers $r,s\in\mathbb{Z}$ such that $1\leq r\leq p-1$
and $2\leq s\leq p-1$ and then computes $y_{A}=z^{r}x^{s}z^{-r}$, and sends
$y_{A}\in H_{p}$ to Bob.

  3. 3.

Bob picks two secret integers $u,v\in\mathbb{Z}$ such that $1\leq u\leq p-1$
and $2\leq v\leq p-1$ and then computes $y_{B}=z^{u}x^{v}z^{-u}$, and sends
$y_{B}\in H_{p}$ to Alice.

  4. 4.

Alice computes $K_{A}=z^{r}{y_{B}}^{s}z^{-r}$ as the shared session key.

  5. 5.

Bob computes $K_{B}=z^{u}{y_{A}}^{v}z^{-u}$ as the shared session key.

We now show how the cryptanalysis for this protocol reduces to breaking
Protocol 2 for $R=\operatorname{Mat}_{2}(\mathbb{F}_{p})$. First, by the
arguments in [27], we have $H/pH=L/pL=H_{p}$. Now, by Proposition 3.3 of [27],
for any integers $a$ and $b$ satisfying $a^{2}+b^{2}\equiv-1\pmod{p}$, the map

$\displaystyle\phi_{a,b}:H/pH$
$\displaystyle\rightarrow\operatorname{Mat}_{2}(\mathbb{Z}/p\mathbb{Z})$
$\displaystyle\gamma_{1}+\gamma_{2}i+\gamma_{3}j+\gamma_{4}k$
$\displaystyle\mapsto\begin{pmatrix}\gamma_{1}+\gamma_{2}a+\gamma_{4}b&\gamma_{3}+\gamma_{4}a-\gamma_{2}b\\\
-\gamma_{3}+\gamma_{4}a-\gamma_{2}b&\gamma_{1}-\gamma_{2}a-\gamma_{4}b.\end{pmatrix}$

is an isomorphism of rings. Clearly, the inverse of $\phi_{a,b}$ is also
easily computed as

$\phi_{a,b}^{-1}\left(\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\right)=\frac{1}{2}(A+D)+\frac{1}{2}\left(b(B+C)-a(A-D)\right)i+\frac{1}{2}(B-C)j-\frac{1}{2}\left(a(B+C)+b(A-D)\right)k$

Thus, Protocol 3 may be treated as if it is over
$\operatorname{Mat}_{2}(\mathbb{F}_{p})$. Now, note that the public keys are
of the form $y=z^{-r}x^{s}z^{r}$ where $r$ and $s$ are private integers, and
$x\in\operatorname{Mat}_{2}(\mathbb{F}_{p})$,
$z\in\operatorname{GL}_{2}(\mathbb{F}_{p})$ are public matrices. The only
difference now with Protocol 2 is that this scheme has two secret integers
instead of one. However, we observe that the presence of two secret integers
weakens the scheme, because an adversary can break the system if they find any
pair of solutions $(r,s)$ such that $K_{A}=z^{r}x^{s}x^{-r}$. So, it makes
sense to fix $s$, without loss of generality, to $s=1$. Thus, Corollary 1 for
the case $n=2$ now shows that finding $r$ and breaking Protocol 3 reduces to
at most four DLPs.

####  3.2.2 Subgroup Conjugacy Search in Matrix Groups

In [9], the authors introduce what they call the Subgroup Conjugacy Search
Problem (SCSP) in a nonabelian group $G$, and propose a protocol based on it,
suggesting as potential platforms the matrix group
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$ and a subgroup of it. We first note
that the SCSP corresponds exactly to the $A$-restricted CSP defined in this
paper, for a cyclic subgroup $A$ of $G$. Therefore, Corollary 1 gives a direct
cryptanalaysis of this protocol, reducing its security to that of a set of
$\mathcal{O}(n^{2})$ DLPs over a small extension of ${\mathbb{F}_{q}}$.

While the authors state that the SCSP is at least as hard as the CSP, we
remark that this is likely not true in general. In Section 2.3 we showed that
in finite polycyclic group with two generators, a well-chosen SCSP is harder
than the CSP, whereas by Remark 1 the SCSP in certain infinite polycyclic
groups with two generators groups is seemingly easier than the CSP. Similarly,
Section 3.1 gives a complete reduction of the SCSP in
$\operatorname{GL}_{n}({\mathbb{F}_{q}})$ to a set of DLPs, but a solution to
the general CSP is unclear. This may be intuitively realized, since while
there is an added constraint in the SCSP, the adversary also has more
information on where to search for the conjugator.

##  4 Conclusion

In this paper, we produced a polynomial time solution for the CSP in a finite
polycyclic group with two generators, and showed that a restricted CSP is
reducible to a DLP. In matrix groups over finite fields, we used the Jordan
decomposition of a matrix to produce a polynomial time reduction of an
$A$-restricted CSP, where $A\subseteq GL({\mathbb{F}_{q}})$ is a cyclic
subgroup, to a set of DLPs over an extension of ${\mathbb{F}_{q}}$. We also
used this theory to cryptanalyse the systems proposed in [9], [25], and [28].
More generally, a direct consequence of our results is that the security of a
protocol based on an $A$-restricted CSP, where $A$ is cyclic, which uses a
linear platform group, essentially depends on the difficulty of computing a
representation of the platform, and a set of DLPs. We believe that our methods
and findings are likely to allow for several other heuristic attacks in the
general case.

## References

  * [1] Iris Anshel, Michael Anshel, and Dorian Goldfeld.  An algebraic method for public-key cryptography.  Math. Res. Lett., 6(3-4):287–291, 1999.
  * [2] Adi Ben-Zvi, Arkadius Kalka, and Boaz Tsaban.  Cryptanalysis via algebraic spans.  In Annual International Cryptology Conference, pages 255–274. Springer, 2018.
  * [3] Li Chen and Bin Fu.  Linear and sublinear time algorithms for basis of abelian groups.  In Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC ’09, page 493–502, Berlin, Heidelberg, 2009. Springer-Verlag.
  * [4] Bettina Eick and Delaram Kahrobaei.  Polycyclic groups: a new platform for cryptology?  arXiv preprint arXiv:0411077, 2004.
  * [5] Benjamin Fine, Maggie Habeeb, Delaram Kahrobaei, and Gerhard Rosenberger.  Aspects of nonabelian group based cryptography: a survey and open problems.  arXiv preprint arXiv:1103.4093, 2011.
  * [6] David Freeman.  The discrete logarithm problem in matrix groups.  2004\.
  * [7] Volker Gebhardt.  Efficient collection in infinite polycyclic groups.  Journal of Symbolic Computation, 34(3):213–228, 2002.
  * [8] Jonathan Gryak and Delaram Kahrobaei.  The status of polycyclic group-based cryptography: A survey and open problems.  Groups Complexity Cryptology, 8(2):171–186, 2016.
  * [9] Lize Gu and Shihui Zheng.  Conjugacy systems based on nonabelian factorization problems and their applications in cryptography.  J. Appl. Math., 2014:630607:1–630607:10, 2014.
  * [10] Dennis Hofheinz and Rainer Steinwandt.  A practical attack on some braid group based cryptographic primitives.  In Public Key Cryptography — PKC 2003, pages 187–198, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
  * [11] Derek F Holt, Bettina Eick, and Eamonn A O’Brien.  Handbook of computational group theory.  CRC Press, 2005.
  * [12] Ilic.  Discrete logs in arbitrary finite groups.  PhD thesis, Florida Atlantic University, 2008.
  * [13] Sunil Kumar Kashyap, Birendra Sharma, and Amitabh Banerjee.  A cryptosystem based on DLP $\gamma=\alpha^{a}\beta^{b}\mod p$.  International Journal of Network Security, 3:95–100, 01 2006.
  * [14] Lee C Klingler, Spyros S Magliveras, Fred Richman, and Michal Sramka.  Discrete logarithms for finite groups.  Computing, 85(1-2):3, 2009.
  * [15] Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, and Choonsik Park.  New public-key cryptosystem using braid groups.  In Annual International Cryptology Conference, pages 166–183. Springer, 2000.
  * [16] Martin Kreuzer, Alexey D Myasnikov, and Alexander Ushakov.  A linear algebra attack to group-ring-based key exchange protocols.  In International Conference on Applied Cryptography and Network Security, pages 37–43. Springer, 2014.
  * [17] Gérard Maze, Chris Monico, and Joachim Rosenthal.  Public key cryptography based on semigroup actions.  Adv. in Math. of Communications, 1(4):489–507, 2007.
  * [18] Alfred Menezes and Yihong Wu.  The discrete logarithm problem in $GL(n,q)$.  Ars Comb., 47, 1997.
  * [19] Chandrashekhar Meshram.  A cryptosystem based on double generalized discrete logarithm problem.  Int. J. Contemp. Math. Sciences, 6:285–297, 01 2011.
  * [20] Alexei Myasnikov and Vitaliĭ Roman’kov.  A linear decomposition attack.  Groups Complexity Cryptology, 7(1):81–94, 2015.
  * [21] Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov.  Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol.  In Public Key Cryptography - PKC 2006, pages 302–314, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [22] Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov.  Group-based cryptography.  Springer Science & Business Media, 2008.
  * [23] T. N. Shorey and R. Tijdeman.  Exponential Diophantine Equations.  Cambridge Tracts in Mathematics. Cambridge University Press, 1986.
  * [24] Vladimir Shpilrain and Alexander Ushakov.  A new key exchange protocol based on the decomposition problem.  arXiv preprint arXiv:0512140, 2005.
  * [25] Chang Seng Sin and Huey Voon Chen.  Group-based key exchange protocol based on complete decomposition search problem.  In Information Security Practice and Experience. Springer International Publishing, 2019.
  * [26] Boaz Tsaban.  Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography.  Journal of Cryptology, 28(3):601–622, 2015.
  * [27] Nikolaos Tsopanidis.  The Hurwitz and Lipschitz Integers and Some Applications.  PhD thesis, Universidade do Porto, 2020.
  * [28] Maheswara Rao Valluri and Shailendra Vikash Narayan.  Quaternion public key cryptosystems.  In 2016 World Congress on Industrial Control Systems Security (WCICSS), pages 1–4, 2016.
  * [29] Michael R. Vaughan-Lee.  Collection from the left.  J. Symb. Comput., 9:725–733, 1990.