capbtabboxtable[][]

# Cryptanalysis of a System based on
Twisted Dihedral Group Algebras

Simran Tinani This research is supported by armasuisse Science and Technology.

###### Abstract

Several cryptographic protocols constructed based on less-known algorithmic
problems, such as those in non-commutative groups, group rings, semigroups,
etc., which claim quantum security, have been broken through classical
reduction methods within their specific proposed platforms. A rigorous
examination of the complexity of these algorithmic problems is therefore an
important topic of research. In this paper, we present a cryptanalysis of a
public key exchange system based on a decomposition-type problem in the so-
called twisted group algebras of the dihedral group $D_{2n}$ over a finite
field ${\mathbb{F}_{q}}$. Our method of analysis relies on an algebraic
reduction of the original problem to a set of equations over
${\mathbb{F}_{q}}$ involving circulant matrices, and a subsequent solution to
these equations. Our attack runs in polynomial time and succeeds with
probability at least $90$ percent for the parameter values provided by the
authors. We also show that the underlying algorithmic problem, while based on
a non-commutative structure, may be formulated as a commutative semigroup
action problem.

##  1 Introduction

The design of efficient cryptographic systems that resist quantum attacks
presently constitutes the important area of research called post-quantum
cryptography. Non-commutative structures such as nonabelian groups, group
rings, semigroups, etc., along with pertinent algorithmic problems, have been
used for the construction of public key cryptosystems in a plethora of works
in this field. Two algorithmic problems that have found great mention in this
realm are the so-called conjugacy search problem and the decomposition problem
(see [21], [3], [7]). Since such problems in general cannot be formulated as a
version of the hidden subgroup problem in a finite abelian group, they have
been suggested to render the corresponding cryptographic systems secure from
known quantum attacks. However, specific instances of these problems are often
solvable through other classical methods and do not have the presumed
complexity in the specific suggested platform (see, for instance [23], [1]).
Several linear algebra attacks on such cryptosystems have been devised that
retrieve the shared key, often without solving the underlying algorithmic
problem [24], [14].

In [4], the authors construct a key exchange system based on so-called twisted
group algebras over a finite field ${\mathbb{F}_{q}}$, which are similar to
group algebras but have a more complicated multiplicative structure. Group
algebras have found mention in some other proposed public key cryptographic
schemes. In [9], the authors construct a key exchange protocol based on the
discrete logarithm problem in the semigroup
$\operatorname{Mat}_{3}(\mathbb{F}_{7}[S_{5}])$ of $3\times 3$ matrices over
the group ring $\mathbb{F}_{7}[S_{5}]$, where $S_{5}$ is the group of
permutation on five symbols. In [15], an attack was devised by showing that
$\operatorname{Mat}_{3}(\mathbb{F}_{7}[S_{5}])$ embeds into
$\operatorname{Mat}_{360}(\mathbb{F}_{7})$, for which the discrete logarithm
problem can then be solved using the method in [12] adapted to singular
matrices. The attack in [6] on the same system uses the fact that the algebra
$\mathbb{F}_{7}[S_{5}]$ is semisimple, and so by Maschke’s theorem it is
isomorphic to a direct sum of matrix algebras over $\mathbb{F}_{7}$.

The authors of [4] assert that since Maschke’s Theorem is valid also for
twisted group algebras, a similar attack might break the underlying problem of
their system. However, to resolve this they choose $q$ such that the twisted
group algebra is not semisimple. Further, they assert that the general methods
of cryptanalysis in [17] and [18], which require the construction of bases
over some vector spaces, do not apply to their system. This is attributed to
the facts that the twisted group algebra is not a group under the twisted
multiplication and that there is an added dimension of non-commutativity with
the twisted multiplication.

The underlying platform of the system in [4] is a twisted group algebra of the
dihedral group $D_{2n}$ over a finite field ${\mathbb{F}_{q}}$ with twisted
multiplication defined with the help of a function called a 2-cocycle. The
2-cocycle $\alpha$ is chosen by the authors such that
$\mathbb{F}_{q}^{\alpha}D_{2n}$ and ${\mathbb{F}_{q}}D_{2n}$ are not
isomorphic, so that one is no longer working over a group algebra. Some recent
relevant works on twisted group algebras are [16] and [5]. In [5], the authors
study right ideals of twisted group algebras, endowing them with a natural
distance and thus studying them as codes; they show that that all perfect
linear codes are twisted group codes. In [16], the authors use twisted
dihedral group rings as a platform for a public key protocol as a non-
commutative variation of the Diffie-Hellman protocol. This protocol has a
similar platform to the one in [4], but with the twisted multiplication and
2-cocycle defined differently. The authors show in [4] that the twisted group
algebra platforms are structurally different.

The security of the protocol in [4] relies on a newly introduced algorithmic
assumption, which the authors call Dihedral Product Decomposition (DPD)
Assumption. Under this assumption, the authors prove that their protocol is
session-key secure in the authenticated-links adversarial model of Canetti and
Krawczyk [2]. The underlying algorithmic problem can be seen as a special form
of the decomposition problem over the multiplicative monoid of an algebra $A$:
given $(x,y)\in A$ and $S\subseteq G$, the problem is to find $z_{1},z_{2}\in
S$ such that $y=z_{1}xz_{2}$. The Dihedral Product Decomposition Problem
constitutes finding $(z_{1},z_{2})$ given $z_{1}xz_{2}$ and $x$ in the
platform, where $z_{1}$ and $z_{2}$ lie in specific predefined subalgebras of
$\mathbb{F}_{q}^{\alpha}D_{2n}$. It is therefore a more restricted version of
the general decomposition problem in the platform. The authors claim that the
protocol proposed is quantum-safe, with justification based on the fact that
the decomposition problem is a generalization of the conjugacy search problem,
which is believed to be difficult even for quantum computers, in certain
platform groups.

In this paper we show that in most cases, the underlying Dihedral Product
Decomposition (DPD) Problem can be solved algebraically with a classical
polynomial time algorithm. As a result, the Dihedral Product Decomposition
Assumption does not hold, and the security of the system breaks down
completely. We do this by producing an algebraic reduction of the original
problem to a set of equations over ${\mathbb{F}_{q}}$ involving circulant
matrices, which we show can be solved in polynomial time in a majority of
cases. We show that our algorithm succeeds with probability
$1-(1-\frac{1}{q})^{2}$, which gives a lower bound of a 90 percent success
rate with the values of $q$ and $n$ proposed by the authors. We also show that
the underlying DPD problem may be formulated as a semigroup action problem
[11], with multiplication in the multiplicative monoid of a twisted dihedral
group algebra. Some other protocols using this method have been proposed in
[10], [9], [11].

The paper is structured as follows. In Section 2 we describe the structure and
some properties of the underlying platform, viz. the twisted group algebra
$\mathbb{F}_{q}^{\alpha}D_{2n}$, closely following the results of [4]. In
Section 3, we describe the key exchange protocol proposed in [4] and state the
DPD problem, which forms the basis of its security assumption. We show that
despite the use of a non-commutative structure, this algorithmic problem is
equivalent to a commutative semigroup action problem. In Section 4, we present
some background definitions and results on circulant matrices, which are
needed for our reduction and cryptanalysis. In Section 5, we describe an
algebraic reduction of the DPD problem to a set of simultaneous equations over
${\mathbb{F}_{q}}$ and show that in a majority of cases, they can be solved by
linear algebra in polynomial time. Using these results, we provide a
polynomial time algorithm which performs the cryptanalysis of the system of
[4].

Throughout, we let $\mathbb{F}$ denote a field, $G$ denote a finite group and
${\mathbb{F}_{q}}$ denote the finite field with $q$ elements, where $q$ is a
power of a prime. Also let
$\mathbb{F}_{q}^{*}={\mathbb{F}_{q}}\setminus\\{0\\}$. We denote by $D_{2n}$
the dihedral group of size $2n$.

##  2 Structure of the Platform

######  Definition 1 (Group Algebra).

The group algebra $\mathbb{F}[G]$ is the set of the formal sums
$\sum\limits_{g\in G}a_{g}g$, with $a_{g}\in\mathbb{F}$, $g\in G$. Addition is
defined componentwise: $\sum\limits_{g\in G}a_{g}g+\sum\limits_{g\in
G}b_{g}g:=\sum\limits_{g\in G}(a_{g}+b_{g})g$. Multiplication is defined as
$\sum\limits_{g\in G}a_{g}g\cdot\sum\limits_{g\in G}b_{g}g:=\sum\limits_{g\in
G}\sum\limits_{h\in G}(a_{g}b_{h})gh=\sum\limits_{k\in G}\sum\limits_{g\in
G,\;h\in G:gh=k}a_{g}b_{h}k$.

Clearly, $\mathbb{F}[G]$ is an algebra over $\mathbb{F}$ with dimension $|G|$.
If $G$ is non-commutative, so is $\mathbb{F}[G]$.

In [8], a new form of multiplication on the $\mathbb{F}$-vector space
$\mathbb{F}[G]$ is described, which produces what are called twisted group
algebras, using the concept of 2-cocycles.

######  Definition 2 (2-Cocycle).

A map $\alpha:G\times G\rightarrow\mathbb{F}_{q}^{*}$ is called a 2-cocycle of
$G$ if $\alpha(1,1)=1$ and for all $g,h,k\in G$ we have
$\alpha(g,hk)\alpha(h,k)=\alpha(gh,k)\alpha(g,h)$.

######  Definition 3 (Twisted Group Algebra).

Let $\alpha$ be a 2-cocycle of $G$. The twisted group algebra
$\mathbb{F}^{\alpha}G$ is the set of all formal sums $\sum\limits_{g\in
G}a_{g}g$, where $a_{g}\in\mathbb{F}$, with the following twisted
multiplication: $g\cdot h=\alpha(g,h)gh$, for $g,h\in G$. The multiplication
rule extends linearly to all elements of the algebra: $(\sum\limits_{g\in
G}a_{g}g)\cdot(\sum\limits_{h\in G}b_{h}h)=\sum\limits_{g\in
G}\sum\limits_{h\in G}a_{g}b_{h}\alpha(g,h)gh$. Addition is given
componentwise as in Definition 1.

######  Remark 1.

Throughout the rest of the paper, we will be concerned with twisted group
algebras, and so it is understood that the product $(\sum\limits_{g\in
G}a_{g}g)\cdot(\sum\limits_{h\in G}a_{h}h)$ denotes twisted multiplication.
Further, we will usually omit the $\cdot$ symbol, so that multiplication in
the group $G$ and in the twisted group algebra are not differentiated by
operation notation. To avoid confusion we ensure that the symbols used for
elements of the group and group algebra do not intersect.

Denote the set of all 2-cocycles of $G$ into ${\mathbb{F}_{q}}$ by
$Z^{2}(G,\mathbb{F}_{q}^{*})$. For $\alpha,\beta\in
Z^{2}(G,\mathbb{F}_{q}^{*})$, one may define the cocycle $\alpha\beta\in
Z^{2}(G,\mathbb{F}_{q}^{*})$ by $\alpha\beta(g,h)=\alpha(g,h)\beta(g,h)$ for
all $g,h\in G$. With this operation, $Z^{2}(G,\mathbb{F}_{q}^{*})$ becomes a
multiplicative abelian group.

######  Definition 4 (Adjunct).

For an element $a=\sum\limits_{g\in G}a_{g}g\in\mathbb{F}_{q}^{\alpha}G$ we
define its adjunct as $\hat{a}:=\sum\limits_{g\in
G}a_{g}\alpha(g,g^{-1}))g^{-1}$

###  2.1 A twisted dihedral group algebra

For the rest of this paper, we set $G=D_{2n}$, where $D_{2n}=\langle
x,y:x^{n}=y^{2}=1,yxy^{-1}=x^{-1}\rangle$ is the dihedral group of order $2n$.
Further, we let $C_{n}=\langle x^{i}\rangle$ be the cyclic subgroup of
$D_{2n}$ generated by $x$ and $\alpha$ be a 2-cocycle of $D_{2n}$.

The following lemma from [4] can be verified in a straightforward manner.

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

We have

  1. 1.

$\mathbb{F}_{q}^{\alpha}D_{2n}$ is a free
$\mathbb{F}_{q}^{\alpha}C_{n}$-module with basis $\\{1,y\\}$. Therefore
$\mathbb{F}_{q}^{\alpha}D_{2n}=\mathbb{F}_{q}^{\alpha}C_{n}\oplus\mathbb{F}_{q}^{\alpha}C_{n}y$
as a direct sum of ${\mathbb{F}_{q}}$-vector spaces.

  2. 2.

$\mathbb{F}_{q}^{\alpha}C_{n}y\cong\mathbb{F}_{q}^{\alpha}C_{n}$ as
$\mathbb{F}_{q}^{\alpha}C_{n}$-modules.

  3. 3.

For $a\in\mathbb{F}_{q}^{\alpha}C_{n}y$, $ab\in\mathbb{F}_{q}^{\alpha}C_{n}$
if $b\in\mathbb{F}_{q}^{\alpha}C_{n}y$ and
$ab\in\mathbb{F}_{q}^{\alpha}C_{n}y$ if $b\in\mathbb{F}_{q}^{\alpha}C_{n}$.

  4. 4.

If $a\in\mathbb{F}_{q}^{\alpha}C_{n}$, then
$\hat{a}\in\mathbb{F}_{q}^{\alpha}C_{n}$. Similarly, if
$a\in\mathbb{F}_{q}^{\alpha}C_{n}y$, then
$\hat{a}\in\mathbb{F}_{q}^{\alpha}C_{n}y$.

######  Definition 5.

  1. 1.

For a 2-cocycle $\alpha$ of $D_{2n}$ we define the reversible subspace of
$\mathbb{F}_{q}^{\alpha}C_{n}y$ as the vector subspace

$\Gamma_{\alpha}=\\{a=\sum\limits_{i=0}^{n-1}a_{i}x^{i}y\in\mathbb{F}_{q}^{\alpha}C_{n}y\mid
a_{i}=a_{n-i}\text{ for }i=1,\ldots,n-1\\}.$

  2. 2.

Define a map
$\psi:\mathbb{F}_{q}^{\alpha}C_{n}y\rightarrow\mathbb{F}_{q}^{\alpha}C_{n}$ as
follows. Given
$a=\sum\limits_{i=0}^{n-1}a_{i}x^{i}y\in\mathbb{F}_{q}^{\alpha}C_{n}y$ we
define
$\psi(a)=\sum\limits_{i=0}^{n-1}a_{i}x^{i}\in\mathbb{F}_{q}^{\alpha}C_{n}$.
Clearly, $\psi$ is an ${\mathbb{F}_{q}}$-linear isomorphism.

In this paper, we will refer to an element
$\sum\limits_{i=1}^{n-1}a_{i}x^{i}y$ of the reversible subspace
$\Gamma_{\alpha}$ as a reversible element of $\mathbb{F}_{q}^{\alpha}C_{n}y$
and to the corresponding vector $(a_{0},\ldots,a_{n-1})\in\mathbb{F}_{q}^{n}$
as a reversible vector.

######  Lemma 2 ([4]).

Let $\alpha$ be a 2-cocycle of $D_{2n}$. Then we have

  1. 1.

If

$\alpha(x^{i},x^{j-i})=\alpha(x^{j-i},x^{i})$ (1)

for all $i,j\in\\{0,\ldots,n-1\\}$, then $ab=ba$ for
$a,b\in\mathbb{F}_{q}^{\alpha}C_{n}$.

  2. 2.

If

$\alpha(x^{i-j}y,x^{i-j}y)\alpha(x^{i}y,x^{i-j}y)=\alpha(x^{n-i}y,x^{n-i}y)\alpha(x^{j-i}y,x^{n-i}y)$
(2)

for all $i,j\in\\{0,\ldots,n-1\\}$, then $a\hat{b}=b\hat{a}$ for
$a,b\in\Gamma_{\alpha}$.

The following lemma provides an explicit construction of the 2-cocycle that
will be used throughout in the cryptographic construction of [4].

######  Lemma 3 ([4]).

Let $\lambda\in\mathbb{F}_{q}^{*}={\mathbb{F}_{q}}\setminus\\{0\\}$. The map
$\alpha_{\lambda}:D_{2n}\times D_{2n}\rightarrow\mathbb{F}_{q}^{*}$ defined by

$\displaystyle\alpha_{\lambda}(g,h)$ $\displaystyle=\lambda\ \text{for}\
g=x^{i}y,\ h=x^{j}y\ \text{with}\ i,j\in\\{0,\ldots,n-1\\}\ \text{and}$
$\displaystyle\alpha_{\lambda}(g,h)$ $\displaystyle=1\ \text{otherwise}$ (3)

is a 2-cocycle. Further, $\alpha_{\lambda}$ satisfies the two conditions (1)
and (2).

###### Proof.

By definition, $\alpha_{\lambda}(1,1)=1$. Thus one only needs to verify that
$\alpha_{\lambda}(g,h)\alpha_{\lambda}(gh,k)=\alpha_{\lambda}(g,hk)\alpha_{\lambda}(h,k)$
for all $g,h,k\in D_{2n}$. Write $h=x^{j_{1}}y^{k_{1}}$ and
$k=x^{j_{2}}y^{k_{2}}$ with $i,j_{1},j_{2}\in\\{0,\ldots,n-1\\}$. The
condition may then be directly verified separately in a straightforward way
for the two possible cases $g=x^{i}$ and $g=x^{i}y$. The fact that
$\alpha_{\lambda}$ satisfies conditions (1) and (2) follows from the
definition. ∎

######  Lemma 4 ([4]).

${\mathbb{F}_{q}}D_{2n}$ and ${\mathbb{F}_{q}}^{\alpha_{\lambda}}D_{2n}$ are
isomorphic if and only if $\lambda$ is a square in ${\mathbb{F}_{q}}$, i.e. if
and only if $\lambda^{(q-1)/2}=1$.

######  Lemma 5 ([4]).

If $\lambda_{1},\lambda_{2}$ are not squares in ${\mathbb{F}_{q}}$, then
${\mathbb{F}_{q}}^{\alpha_{\lambda_{1}}}D_{2n}$ and
${\mathbb{F}_{q}}^{\alpha_{\lambda_{2}}}D_{2n}$ are isomorphic.

From Lemma 2 we thus have that for the choice $\alpha=\alpha_{\lambda}$ of
2-cocycle, the multiplicative ring of $\mathbb{F}_{q}^{\alpha}C_{n}$ is
commutative, and that $a\hat{b}=b\hat{a}$ for all $a,b\in\Gamma_{\alpha}$. The
form (3) of $\alpha=\alpha_{\lambda}$ is adopted throughout for the
cryptosystem in [4] and thus we restrict our study to this cocycle. Thus,
henceforth we take $\alpha=\alpha_{\lambda}$.

##  3 The key exchange protocol

Having described the relevant structural properties of the underlying
platform, we now describe the key exchange protocol in [4]. This uses two-
sided multiplications in $\mathbb{F}_{q}^{\alpha}D_{2n}$.

###  3.1 Public parameters

  1. 1.

A number $m\in\mathbb{N}$ and a prime $p>2$ with $p\mid 2n$ and set $q=p^{m}$.

  2. 2.

A 2-cocycle $\alpha=\alpha_{\lambda}$ for a non-square $\lambda$ in
${\mathbb{F}_{q}}$. This ensures that the platform
$\mathbb{F}_{q}^{\alpha}D_{2n}$ is not isomorphic to ${\mathbb{F}_{q}}D_{2n}$.

  3. 3.

An element $h=h_{1}+h_{2}$ for a random $0\neq
h_{1}\in\mathbb{F}_{q}^{\alpha}C_{n}$ and a random $0\neq
h_{2}\in\mathbb{F}_{q}^{\alpha}C_{n}y$. (Clearly, since $h$ is public, so are
$h_{1}$ and $h_{2}$.)

Protocol 1 describes the key exchange protocol of [4].

######  Protocol 1.

  1. 1.

Alice chooses a secret pair
$(s_{1},t_{1})\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$, and sends
$\mathrm{pk}_{A}=s_{1}ht_{1}$ to Bob.

  2. 2.

Bob chooses a secret pair
$(s_{2},t_{2})\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$ and sends
$\mathrm{pk}_{B}=s_{2}ht_{2}$ to Alice.

  3. 3.

Alice computes $K_{A}=s_{1}pk_{B}\hat{t_{1}}$,

  4. 4.

Bob computes $K_{B}=s_{2}pk_{A}\hat{t_{2}}$

  5. 5.

The shared key is $K=K_{A}=K_{B}$

The authors’ proposed values for parameters $q$ and $n$ are $q=n=19$,
$q=n=23$, $q=n=31$, $q=n=41$.

###  3.2 Correctness

It is easy to show that within an uncorrupted session, both Alice and Bob
establish the same key. Indeed, because of the choice of
$\alpha=\alpha_{\lambda}$, we have $s_{i}s_{j}=s_{j}s_{i}$ in
$\mathbb{F}_{q}^{\alpha}C_{n}$ and $t_{i}\hat{t_{j}}=t_{j}\hat{t_{i}}$ in
$\mathbb{F}_{q}^{\alpha}C_{n}y$ for $i,j\in\\{1,2\\}$, so

$K_{A}=s_{1}\mathrm{pk}_{B}\hat{t_{1}}=s_{1}s_{2}ht_{2}\hat{t_{1}}=s_{2}s_{1}ht_{1}\hat{t_{2}}=s_{2}\mathrm{pk}_{A}\hat{t_{2}}=K_{B}.$

###  3.3 Security Assumption

The security of the protocol depends on the assumption of the difficulty of
the following algorithmic problem.

######  Definition 6 (Dihedral Product Decomposition (DPD) Problem).

Let $(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha_{\lambda}}$ be a
secret key. Given a public element
$h=h_{1}+h_{2}\in\mathbb{F}_{q}^{\alpha}D_{2n},\
h_{1}\in\mathbb{F}_{q}^{\alpha}C_{n},\ h_{2}\in\mathbb{F}_{q}^{\alpha}C_{n}y$,
and a public key $\mathrm{pk}=sht$, the DPD problem requires an adversary to
compute
$(\tilde{s},\tilde{t})\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$
such that $\mathrm{pk}=\tilde{s}h\tilde{t}$.

Let $(\tilde{s},\tilde{t})$ be the output of an adversary $\mathcal{A}$
attempting to solve the DPD problem for $\mathbb{F}_{q}^{\alpha}D_{2n}$. The
authors define $\mathcal{A}$’s advantage $DPD_{adv}[\mathcal{A},\
\mathbb{F}_{q}^{\alpha}D_{2n}]$ in solving the DPD problem as the probability
that $\tilde{s}h\tilde{t}=sht$.

######  Definition 7 (DPD Assumption).

The DPD assumption is said to hold for $\mathbb{F}_{q}^{\alpha}D_{2n}$ if for
all efficient adversaries $\mathcal{A}$ the quantity $DPD_{adv}[\mathcal{A},\
\mathbb{F}_{q}^{\alpha}D_{2n}]$ is negligible.

In Section 5, we provide a cryptanalysis of Protocol 1 by solving the DPD
problem. We show that in most cases, a polynomial time solution is possible,
and so the DPD assumption does not hold. For our method of cryptanalysis, we
need some prerequisites on circulant matrices, which we provide in the next
section. However, we first show below how the DPD problem can be formulated as
a special case of a commutative semigroup action problem, in the framework
introduced in [11].

####  3.3.1 DPD problem as a commutative semigroup action

The authors of [4] assert that given a fixed
$h\in\mathbb{F}_{q}^{\alpha}D_{2n}$, the set of keys
$\\{sht\mid(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}\\}$ is
not even a semigroup under the twisted algebra multiplication. From this
observation, they claim that their system is immune to the quantum cycle-
finding algorithm of Shor [20] which is known to solve the hidden subgroup
problem in abelian groups.

Further, the security of the system of [4] is based on the presence of a non-
commutative multiplication in the twisted group algebra. However, we now show
that the DPD problem can be formulated as a commutative semigroup action
problem, and so any classical or quantum solution to the latter also applies
to the former. In [13], a Pollard-rho type square root algorithm was provided
to solve an abelian group action problem, whereas the possibility for a
modification to the commutative semigroup case was left open.

As observed before, the cocycle $\alpha=\alpha_{\lambda}$ satisfies conditions
(1) and (2). Thus, $ab=ba$ for $a,b\in\mathbb{F}_{q}^{\alpha}C_{n}$ and
$a\hat{b}=b\hat{a}$ for $a,b\in\Gamma_{\alpha}$. In particular,
$\mathbb{F}_{q}^{\alpha}C_{n}$ is a commutative subalgebra of
$\mathbb{F}_{q}^{\alpha}D_{2n}$. Recall the ${\mathbb{F}_{q}}$-linear
isomorphism
$\psi:\mathbb{F}_{q}^{\alpha}C_{n}\rightarrow\mathbb{F}_{q}^{\alpha}C_{n}y$
given by
$\psi(a)=\sum\limits_{i=0}^{n-1}a_{i}x^{i}\in\mathbb{F}_{q}^{\alpha}C_{n}$ for
$a=\sum\limits_{i=0}^{n-1}a_{i}x^{i}y\in\mathbb{F}_{q}^{\alpha}C_{n}y$. Notice
that $\psi(\Gamma_{\alpha})$ is a commutative semigroup under the
multiplication defined by
$\psi(t)\star\psi(t^{\prime}):=t\hat{t^{\prime}}\in\psi(\Gamma_{\alpha})$.

We can now look at the key exchange in Protocol 1 as an instance of a
semigroup action problem, introduced in [11].

######  Definition 8 (Semigroup Action Problem).

Let $S$ be any semigroup acting on a set $X$

$\displaystyle S\times X\rightarrow X$ $\displaystyle(s,x)\mapsto s\cdot x$

Given an element $y=s\cdot x\in X$, where $x\in X$ is known and $s\in S$ is a
secret, the semigroup action problem is to find some $\tilde{s}\in S$ such
that $\tilde{s}\cdot x=y$.

######  Proposition 1.

The commutative semigroup
$\mathbb{F}_{q}^{\alpha}C_{n}\times\psi(\Gamma_{\alpha})$ acts on
$\mathbb{F}_{q}^{\alpha}D_{2n}$ as follows

$\displaystyle(\mathbb{F}_{q}^{\alpha}C_{n}\times\psi(\Gamma_{\alpha}))\times\mathbb{F}_{q}^{\alpha}D_{2n}$
$\displaystyle\rightarrow\mathbb{F}_{q}^{\alpha}D_{2n}$
$\displaystyle(s,\psi(t))\cdot h$ $\displaystyle=sht$ (4)

###### Proof.

Clearly, $(1,1)\cdot h=h$ for all $h\in\mathbb{F}_{q}^{\alpha}D_{2n}$.
Further,

$(s,\psi(t))((s^{\prime},\psi(t^{\prime}))\cdot
h)=ss^{\prime}ht^{\prime}\hat{t}=ss^{\prime}ht\hat{t^{\prime}}=(ss^{\prime},t\hat{t^{\prime}})\cdot
h=(ss^{\prime},\psi(t)\star\psi(t^{\prime}))\cdot h.$

∎

######  Lemma 6.

The DPD problem is equivalent to the semigroup action problem for the
commutative semigroup action (1)

###### Proof.

Clearly, $t$ and $\psi(t)$ can easily be read from each other without any
significant computational cost. Suppose that given public element $h$ and
public key $\mathrm{pk}$, the adversary can find $s,t$ such that
$sht=\mathrm{pk}$. Then, $(s,\psi(t))$ is a solution to the SAP (1).
Conversely, any solution $(s,\psi(t))$ of the SAP (1) gives the solution
$(s,t)$ of the DPD problem. ∎

The next section highlights some prerequisites on circulant matrices which
will be used in the cryptanalysis of the system in Section 5.

##  4 Circulant Matrices

######  Definition 9.

A matrix over ${\mathbb{F}_{q}}$ of the form
$\begin{pmatrix}c_{0}&c_{n-1}&\ldots&c_{1}\\\ c_{1}&c_{0}&\ldots&c_{2}\\\
\vdots&\vdots&\ddots&\vdots\\\ c_{n-1}&c_{n-2}&\ldots&c_{0}\\\ \end{pmatrix}$
with $c_{i}\in{\mathbb{F}_{q}}$, is called circulant. Given a vector
$\mathbf{c}=(c_{0},c_{1},\ldots,c_{n-1})^{T}\in\mathbb{F}_{q}^{n}$, we use the
notation $M_{\mathbf{c}}$ to denote the circulant matrix
$M_{\mathbf{c}}:=\begin{pmatrix}c_{0}&c_{n-1}&\ldots&c_{1}\\\
c_{1}&c_{0}&\ldots&c_{2}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{n-1}&c_{n-2}&\ldots&c_{0}\\\ \end{pmatrix}$.

######  Definition 10.

Given vectors
$\mathbf{b}=(b_{0},b_{1},\ldots,b_{n-1})^{T}\in\mathbb{F}_{q}^{n}$,
$\mathbf{c}=(c_{0},c_{1},\ldots,c_{n-1})^{T}\in\mathbb{F}_{q}^{n}$, define,
for $0\leq\ell\leq n-1$ the constants

$z_{\ell}({\mathbf{b},\mathbf{c}})=\sum\limits_{i+j=\ell\mod
n}b_{i}c_{j}=\begin{pmatrix}c_{\ell},&c_{\ell-1},&\ldots,&c_{\ell+1}\end{pmatrix}\cdot\begin{pmatrix}b_{0}\\\
b_{1}\\\ \vdots\\\ b_{n-1}\end{pmatrix},0\leq\ell\leq n-1.$

Also define the vector
$\mathbf{z}_{\mathbf{b},\mathbf{c}}=(z_{0}({\mathbf{b},\mathbf{c}}),\ldots,z_{\ell}({\mathbf{b},\mathbf{c}}),\ldots,z_{n-1}({\mathbf{b},\mathbf{c}}))^{T}$.
In other words,

$\mathbf{z}_{\mathbf{b},\mathbf{c}}=\begin{pmatrix}c_{0}&\ldots&c_{1}\\\
c_{1}&\ldots&c_{2}\\\ \vdots&\ddots&\vdots\\\ c_{n-1}&\ldots&c_{0}\\\
\end{pmatrix}\cdot\begin{pmatrix}b_{0}\\\ b_{1}\\\ \vdots\\\
b_{n-1}\end{pmatrix}=M_{\mathbf{c}}\cdot\mathbf{b}.$

As in Definition 9, denote by $M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})$ the
circulant matrix
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})=\begin{pmatrix}z_{0}({\mathbf{b},\mathbf{c}})&\ldots&z_{1}({\mathbf{b},\mathbf{c}})\\\
z_{1}({\mathbf{b},\mathbf{c}})&\ldots&z_{2}({\mathbf{b},\mathbf{c}})\\\
\vdots&\ddots&\vdots\\\
z_{n-1}({\mathbf{b},\mathbf{c}})&\ldots&z_{0}({\mathbf{b},\mathbf{c}})\\\
\end{pmatrix}$. The following result is easy to verify by direct computation.

######  Lemma 7.

$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})=M_{\mathbf{c}}\cdot M_{\mathbf{b}}$.

###  4.1 Probability of a circulant matrix being invertible

We will require the invertibility of some random circulant matrices over
${\mathbb{F}_{q}}$ for our reduction of the system. For this reason, we
discuss the criteria for a random circulant matrix being invertible, and study
this probability. We have the following result from [19].

######  Proposition 2 ([19]).

Let $x^{n}-1=f_{1}^{\alpha_{1}}(x)\ldots f_{\tau}^{\alpha_{\tau}}(x)$ be the
factorization of $x^{n}-1$ over ${\mathbb{F}_{q^{m}}}$ into powers of
irreducible factors. The number of invertible circulant matrices in
$Mat_{n}({\mathbb{F}_{q^{m}}})$ is equal to
$\prod\limits_{i=1}^{\tau}(q^{md_{i}\alpha_{i}}-q^{md_{i}(\alpha_{i}-1)})$,
where $d_{i}$ is the degree of $f_{i}(x)$ in the factorization of $x^{n}-1$.

Note that the number of circulant matrices over ${\mathbb{F}_{q^{m}}}$ is
$q^{mn}$. As a direct consequence, the probability of a randomly chosen
circulant matrix over ${\mathbb{F}_{q^{m}}}$ being invertible is

$\prod\limits_{i=1}^{\tau}\dfrac{q^{md_{i}\alpha_{i}-q^{md_{i}(\alpha_{i}-1)}}}{q^{nm}}=\prod\limits_{i=1}^{\tau}\left(1-\frac{1}{q^{md_{i}}}\right)$

It is now easy to see that a lower bound for this quantity is
$(1-\frac{1}{q^{m}})^{n}$, which is achieved if $x^{n}-1$ splits into distinct
linear factors, i.e. $\tau=n$, $d_{i}=1$, $\alpha_{i}=1$. Similarly, an upper
bound is achieved when there is a single factor in the factorization, i.e.
$\tau=1$ and $\alpha_{1}=n$, in which case the quantity is
$(1-\frac{1}{q^{m}})$. Note that this upper bound is achieved when the
characteristic $p$ of ${\mathbb{F}_{q^{m}}}$ divides $n$
($x^{n}-1=(x-1)^{n}\mod p$). Thus, we have the following corollary.

######  Corollary 1.

If $p\mid n$ then the probability that a randomly chosen $n\times n$ circulant
matrix over ${\mathbb{F}_{q}}$ is invertible is $1-\frac{1}{q}$.

In [4], the authors deliberately choose the case $p\mid n$, so as to avoid
having ${\mathbb{F}_{q^{m}}}D_{2n}$ semisimple, and so, the probability
$1-\frac{1}{q}$ applies for a random circulant matrix being invertible.

##  5 Cryptanalysis

Note that the adversary is given an equation of the form $sht=\gamma$ over
$\mathbb{F}_{q}^{\alpha}D_{2n}$, where

$s=\sum\limits_{i=0}^{n-1}{a_{i}x^{i}}\in\mathbb{F}_{q}^{\alpha}C_{n},\
t=\sum\limits_{i=0}^{n-1}{b_{i}x^{i}y}\in\Gamma_{\alpha}\subseteq{\mathbb{F}_{q}}^{\alpha_{\lambda}}D_{2n}$
(5)

are unknown, and
$h=\sum\limits_{i=0}^{n-1}c_{i}x^{i}+\sum\limits_{i=0}^{n-1}d_{i}x^{i}y$ is
known. Since $t\in\Gamma_{\alpha}$, the coefficients in $t$ satisfy
$b_{k}=b_{n-k}$ for $k=1,\ldots,n-1$. We write

$\gamma=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y}$

for known constants $v_{i},w_{i}$. Substituting the above expansions into the
equation $sht=\gamma$, we have

$\displaystyle(\sum\limits_{i=0}^{n-1}{a_{i}x^{i}})(\sum\limits_{i=0}^{n-1}{c_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{d_{i}x^{i}y})(\sum\limits_{i=0}^{n-1}{b_{i}x^{i}y})=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y}$
$\displaystyle\implies(\sum\limits_{i,j=0}^{n-1}{a_{i}c_{j}x^{i+j}}+\sum\limits_{i,j=0}^{n-1}{a_{i}d_{j}x^{i+j}y})(\sum\limits_{k=0}^{n-1}{b_{k}x^{k}y})=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y}$
$\displaystyle\implies\sum\limits_{i,j,k=0}^{n-1}{a_{i}c_{j}b_{k}x^{i+j+k}y}+\sum\limits_{i,j,k=0}^{n-1}{a_{i}d_{j}b_{k}\lambda
x^{i+j+k}}=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y}$

Comparing coefficients, we have the following two equations

$\sum\limits_{i,j,k=0}^{n-1}{a_{i}c_{j}b_{k}x^{i+j+k}y}=\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y},$
(6)
$\lambda\sum\limits_{i,j,k=0}^{n-1}{a_{i}d_{j}b_{k}x^{i+j+k}}=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}$
(7)

Define vectors $\mathbf{a}=(a_{0},\ldots,a_{n-1})^{T}$,
$\mathbf{b}=(b_{0},\ldots,b_{n-1})^{T}$,
$\mathbf{c}=(c_{0},\ldots,c_{n-1})^{T}$,
$\mathbf{d}=(d_{0},\ldots,d_{n-1})^{T}$,
$\mathbf{w}=(w_{0},\ldots,w_{n-1})^{T}$,
$\mathbf{v}=(v_{0},\ldots,v_{n-1})^{T}$ in $\mathbb{F}_{q}^{n}$. The vectors
$\mathbf{a}$ and $\mathbf{b}$ are unknown to the adversary, while
$\mathbf{c}$, $\mathbf{d}$, $\mathbf{v}$, and $\mathbf{w}$ are publicly known.

###  5.1 Reduction to matrix equations

The following lemma shows that Equation (6) can be reduced to a matrix
equation over ${\mathbb{F}_{q}}$.

######  Lemma 8.

Equation (6) is equivalent to the matrix equation
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\cdot\mathbf{a}=\mathbf{w}$ over
${\mathbb{F}_{q}}$.

###### Proof.

Equating the coefficients of the basis vectors $x^{i}y$ in Equation (6), we
have

$\displaystyle w_{i}=$ $\displaystyle\sum\limits_{\ell=0}^{n-1}\
\sum\limits_{(j,k)\mid j+k=\ell\mod n}{c_{j}}b_{k}a_{i-\ell}$ $\displaystyle=$
$\displaystyle\sum\limits_{\ell=0}\ \sum\limits_{(j,k)\mid j+k=i-\ell\mod
n}{c_{j}}b_{k}a_{\ell}$ $\displaystyle=$
$\displaystyle\begin{pmatrix}z_{i}(\mathbf{b},\mathbf{c})&z_{i-1}(\mathbf{b},\mathbf{c})&\ldots&z_{0}(\mathbf{b},\mathbf{c})&z_{n-1}(\mathbf{b},\mathbf{c})&\ldots&z_{i+1}(\mathbf{b},\mathbf{c})\end{pmatrix}\cdot\mathbf{a}$

Thus, we can rewrite Equation (6) equivalently as the system

$\displaystyle w_{0}=$
$\displaystyle\begin{pmatrix}z_{0}(\mathbf{b},\mathbf{c})&z_{n-1}(\mathbf{b},\mathbf{c})&\ldots&z_{1}({\mathbf{b},\mathbf{c}})\end{pmatrix}\cdot\mathbf{a}$
$\displaystyle w_{1}=$
$\displaystyle\begin{pmatrix}z_{1}(\mathbf{b},\mathbf{c})&z_{0}(\mathbf{b},\mathbf{c})&\ldots&z_{2}(\mathbf{b},\mathbf{c})\end{pmatrix}\cdot\mathbf{a}$
$\displaystyle\vdots$ $\displaystyle w_{n-1}=$
$\displaystyle\begin{pmatrix}z_{n-1}({\mathbf{b},\mathbf{c}})&z_{n-2}({\mathbf{b},\mathbf{c}})&\ldots&z_{0}({\mathbf{b},\mathbf{c}})\end{pmatrix}\cdot\mathbf{a}$

In other words,
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\cdot\mathbf{a}=\mathbf{w}$. ∎

One may similarly rewrite Equation (7) as above, so that we have the following
lemma.

######  Lemma 9.

Equation (7) is equivalent to the matrix equation $\lambda
M_{\mathbf{z}}(\mathbf{b},\mathbf{d})\cdot\mathbf{a}=\mathbf{v}$ over
${\mathbb{F}_{q}}$.

Combining the results of Lemmas 8 and 9, if the vectors
$\mathbf{b}$,$\mathbf{c}$ and $\mathbf{d}$ are given, then $\mathbf{a}$ is a
simultaneous solution to the matrix equations
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\cdot\mathbf{a}=\mathbf{w}$ and
$\lambda M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})\cdot\mathbf{a}=\mathbf{v}$.
However, a priori the vector $\mathbf{b}$ is unknown to the adversary. If we
can find $\mathbf{b}$ such that this system of equations has a simultaneous
solution, then we are done with reducing the DPD problem to a solving a single
system of linear equations, which can be done in polynomial time. Summarizing
this discussion, we have the following result.

######  Proposition 3.

Suppose that a vector $\mathbf{b}=(b_{0},\ldots,b_{n-1})$ is such that the
system of simultaneous equations $\lambda
M_{\mathbf{z}}(\mathbf{b},\mathbf{d})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\mathbf{a}=\mathbf{w}$ has a
simultaneous solution $\mathbf{a}=(a_{0},\ldots,a_{n-1})$. Then,
$s=\sum\limits_{i=0}^{n-1}a_{i}x^{i}$, $t=\sum\limits_{i=0}^{n-1}b_{i}x^{i}y$
is a solution of the equation $sht=\gamma$.

Now, for an adversary, the vectors $\mathbf{a}$ and $\mathbf{b}$ are both
unknown. We will show below that in most cases, it suffices for the adversary
to fix a suitable value for $\mathbf{b}$ and then proceed to solve any one of
the linear equations in Lemmas 8 and 9 for $\mathbf{a}$. More precisely, we
show that if $M_{\mathbf{c}}$ and $M_{\mathbf{d}}$ are invertible, then a
solution is possible for any randomly chosen $\mathbf{b}\in\Gamma_{\alpha}$
for which the correponding circulant matrix $M_{\mathbf{b}}$ is invertible.
Since the values arise from a legitimate public key, we know that there exists
a vector $\mathbf{b}\in\Gamma_{\alpha}$ such that the equations $\lambda
M_{\mathbf{z}}(\mathbf{b},\mathbf{d})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\mathbf{a}=\mathbf{w}$ have a
simultaneous solution $\mathbf{a}$.

######  Proposition 4.

Let the vectors $\mathbf{c}$ and $\mathbf{d}$ be such that $M_{\mathbf{c}}$
and $M_{\mathbf{d}}$ are invertible. Assume that at least one simultaneous
solution $(\mathbf{a},\mathbf{b})$ exists to the matrix equations $\lambda
M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}(\mathbf{b},\mathbf{c})\mathbf{a}=\mathbf{w}$. Then, for any
randomly chosen $\mathbf{b}\in\Gamma_{\alpha}$ such that $M_{\mathbf{b}}$ is
invertible, the equations $\lambda
M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}(\mathbf{b},\mathbf{c})\mathbf{a}=\mathbf{w}$ have a
simultaneous solution $\mathbf{a}$ computable in polynomial time.

###### Proof.

Here, $\mathbf{b}$, $\mathbf{c}$, and $\mathbf{d}$ are invertible, and thus so
are $M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})=M_{\mathbf{d}}\cdot
M_{\mathbf{b}}$ and $M_{\mathbf{z}}(\mathbf{b},\mathbf{c})=M_{\mathbf{c}}\cdot
M_{\mathbf{b}}$. Now, we know that a solution $(\mathbf{a},\mathbf{b})$
exists, and so for some vectors $\mathbf{a}$ and $\mathbf{b}$ we have

$\displaystyle\lambda M_{\mathbf{d}}M_{\mathbf{b}}\mathbf{a}=\mathbf{v},\quad
M_{\mathbf{c}}M_{\mathbf{b}}\mathbf{a}=\mathbf{w},\
i.e.\;\lambda^{-1}M_{\mathbf{d}}^{-1}\mathbf{v}=M_{\mathbf{b}}\mathbf{a},\
M_{\mathbf{c}}^{-1}\mathbf{w}=M_{\mathbf{b}}\mathbf{a}$

So, independently of $\mathbf{a}$ and $\mathbf{b}$ we necessarily have

$\displaystyle\lambda^{-1}M_{\mathbf{d}}^{-1}\mathbf{v}=M_{\mathbf{c}}^{-1}\mathbf{w}$
(8)

Now let $\mathbf{b}$ be any random vector such that $M_{\mathbf{b}}$ is
invertible. Multiplying equation (8) by $M_{\mathbf{b}}^{-1}$, we get

$\displaystyle\lambda^{-1}M_{\mathbf{b}}^{-1}M_{\mathbf{d}}^{-1}\mathbf{v}=M_{\mathbf{b}}^{-1}M_{\mathbf{c}}^{-1}\mathbf{w}$
$\displaystyle\implies\lambda^{-1}M_{\mathbf{z}}(\mathbf{b},\mathbf{d})^{-1}\mathbf{v}=M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})^{-1}\mathbf{w}$

Setting
$\mathbf{a}:=\lambda^{-1}M_{\mathbf{z}}(\mathbf{b},\mathbf{d})^{-1}M_{\mathbf{v}}=M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})^{-1}\mathbf{w}$,
we get $\mathbf{a}$ as the simultaneous solution $\lambda
M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})\mathbf{a}=\mathbf{w}$. ∎

###  5.2 The algorithm for cryptanalysis

We have the following result.

######  Corollary 2.

If $M_{\mathbf{c}}$ and $M_{\mathbf{d}}$ are invertible and $\gamma$ is a
legitimate public key, then the equation $sht=\gamma$ in the unknowns
$s\in\mathbb{F}_{q}^{\alpha}C_{n},\ t\in\Gamma_{\alpha}$ can be solved in
polynomial time for a legitimate secret key $(s,t)$.

###### Proof.

Since $\gamma$ is a legitimate public key, a least one simultaneous solution
$(\mathbf{a},\mathbf{b})$ exists (the one corresponding to the initial secret
key) to the matrix equations $\lambda
M_{\mathbf{z}}({\mathbf{b},\mathbf{d}})\mathbf{a}=\mathbf{v}$ and
$M_{\mathbf{z}}(\mathbf{b},\mathbf{c})\mathbf{a}=\mathbf{w}$. Now, from
Corollary 1, a vector $\mathbf{b}\in\mathbb{F}_{q}^{n}$ such that $\mathbf{b}$
is invertible can be found in an expected $\frac{1}{1-\frac{1}{q}}$ number of
steps. For the solution of the DPD problem, one further requires that the
vector $\mathbf{b}$ satisfies $b_{i}=b_{n-1}$ for $1\leq i\leq n-1$, i.e. that
$\mathbf{b}\in\Gamma_{\alpha}$. However, it is prudent to assume that the
probability of invertibility remains approximately the same on these
reversible vectors. Thus, by Proposition 4, we can set $b$ to be any vector in
$\Gamma_{\alpha}$ such that $M_{\mathbf{b}}$ is invertible. The expected
number of steps before such a $\mathbf{b}$ is found is
$\frac{1}{1-\frac{1}{q}}$, which is very close to 1, and thus takes time
$\mathcal{O}(1)$. This is also confirmed by experimental results, where
randomly chosen symmetric vectors $\mathbf{b}\in\Gamma_{\alpha}$ were
invertible in almost all trials. Once such a vector $\mathbf{b}$ is found, one
computes
$\mathbf{a}=\lambda^{-1}M_{\mathbf{z}}(\mathbf{b},\mathbf{d})^{-1}M_{\mathbf{v}}=M_{\mathbf{z}}({\mathbf{b},\mathbf{c}})^{-1}\mathbf{w}$
in polynomial time. By Proposition 3, this gives a solution to the DPD problem
$sht=\gamma$. ∎

We now state an algorithm to cryptanalyze the key exchange. Its correctness
follows from the above discussion.

Input Parameter $\lambda$ and the cocycle $\alpha=\alpha_{\lambda}$, public
element
$h=\sum\limits_{i=0}^{n-1}c_{i}x^{i}+\sum\limits_{i=0}^{n-1}d_{i}x^{i}y$,
public key
$\gamma=\sum\limits_{i=0}^{n-1}{v_{i}x^{i}}+\sum\limits_{i=0}^{n-1}{w_{i}x^{i}y}$.

Output A solution $(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$
satisfying $sht=\gamma$. This tuple is a solution to the DPD problem.

1: Define vectors in $\mathbb{F}_{q}^{n}$:
$\mathbf{c}=(c_{0},\ldots,c_{n-1})$, $\mathbf{d}=(d_{0},\ldots,d_{n-1})$,
$\mathbf{v}=(v_{0},\ldots,v_{n-1})$, $\mathbf{w}=(w_{0},\ldots,w_{n-1})$.

2: If $M_{\mathbf{c}}$ or $M_{\mathbf{d}}$ is not invertible

Return Fail

3: Pick a vector $\mathbf{b}=(b_{0},\ldots,b_{n-1})\leftarrow\Gamma_{\alpha}$
at random.

4: If $M_{\mathbf{b}}$ is not invertible, repeat step (3). If it is
invertible, go to step (5).

5: Compute
$\mathbf{a}=\lambda^{-1}M_{\mathbf{z}}(\mathbf{b},\mathbf{c})^{-1}\mathbf{w}=M_{\mathbf{b}}^{-1}M_{\mathbf{d}}^{-1}\mathbf{v}$.

6: With $\mathbf{a}=(a_{0},\ldots,a_{n-1})$, set
$s=\sum_{i=0}^{n-1}a_{i}x^{i}$ and $t=\sum_{i=0}^{n-1}b_{i}x^{i}y$.

7: Return $(s,t)$.

Algorithm 1 Cryptanalysis of Key Exchange over $\mathbb{F}_{q}^{\alpha}D_{2n}$

######  Remark 2.

The solution $(s,t)$ to the DPD returned by Algorithm 1 and referenced in
Corollary 2 is a legitimate secret key, but not necessarily the same as the
originally chosen secret key. In fact, as is clear from the discussion above,
$t=\sum\limits_{i=0}^{n-1}b_{i}x^{i}y\in\Gamma_{\alpha}$ can be selected at
random, and a solution for $s\in\mathbb{F}_{q}^{\alpha}C_{n}$ is found long as
$M_{\mathbf{b}}$ is invertible..

Now, since $\mathbf{c}$ and $\mathbf{d}$ are random in $\mathbb{F}_{q}^{n}$,
the circulant matrices $M_{\mathbf{c}}$ and $M_{\mathbf{d}}$ are invertible
with high probability. The probability that the algorithm fails is the
probability that at least one of them is not invertible, which is given by
$1-(1-\frac{1}{q})^{2}$. Clearly this quantity shrinks with increasing values
of $q$ and $n$. In [4] the smallest values of these parameters are $q=n=19$,
for which this probability is $\approx 0.1$. Thus, Algorithm 1 succeeds in
cryptanalyzing the system with a probability of at least 90 percent.

An immediate corollary of the above argument is that the two-sided
multiplication action

$(\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha})\times\mathbb{F}_{q}^{\alpha}D_{2n}\rightarrow\mathbb{F}_{q}^{\alpha}D_{2n}$
$(s,t)\cdot h\mapsto sht,\ s\in\mathbb{F}_{q}^{\alpha}C_{n},\
t\in\Gamma_{\alpha}$

is far from being injective, contrary to the assumption of the authors. In
fact, for most values of $t$ and $\gamma\in\mathbb{F}_{q}^{\alpha}D_{2n}$,
there is a unique pre-image $s\in\mathbb{F}_{q}^{\alpha}C_{n}$ such that
$sht=\gamma$. Thus, the probability that random choosing yields the right
solution is not $1/|\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}|$, as
claimed by the authors. The real probability is greater than or equal to
probability that the matrices $M_{\mathbf{c}}$ and $M_{\mathbf{d}}$ are
invertible and that the correct value of $s$ corresponding to $t$ is chosen,
which is $\approx 1/|\mathbb{F}_{q}^{\alpha}C_{n}|$ (we already saw that the
probability of the matrices being invertible is very close to 1). From this,
one also sees that the run time of an exhaustive search would be linear in
$|\mathbb{F}_{q}^{\alpha}C_{n}|=p^{nm}$, rather than in
$|\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}|=p^{nm}p^{m\lfloor\frac{n+1}{2}\rfloor}$,
as claimed by the authors of [4].

###  5.3 Examples

In this subsection, we present some examples generated by computer search,
using the algebra software package SageMath [22]. For the structure of the
twisted group algebra and the generation of the keys, we made use of the
original source code of the authors. Our entire working code including the
cryptanalysis can be found at: https://github.com/simran-tinani/Cryptanalysis-
of-twisted-group-algebra-system

In the following examples, an element
$\sum\limits_{i=0}^{n-1}a_{i}x^{i}+\sum\limits_{i=0}^{n-1}b_{i}x^{i}y$ of
$\mathbb{F}_{q}^{\alpha}D_{2n}$ is denoted by the $2n$-tuple
$(a_{0},\ldots,a_{n-1},b_{0},\ldots,b_{n-1})$.

######  Example 1.

For parameters $n=23,\ q=23$, $\lambda=11$, and using the notations above,
consider the randomly generated public element $h$, and secret key
$(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$.

$\displaystyle h=$
$\displaystyle(19,9,4,14,6,13,21,18,18,10,9,2,5,15,13,22,18,13,16,20,11,2,11,6,18,7,17,8,20,20,17,7,15,1,11,9,17,4,11,16,$
$\displaystyle 5,17,19,18,19,20),$ $\displaystyle s=$
$\displaystyle(20,17,20,22,18,18,11,12,2,3,18,11,2,18,3,14,10,2,13,14,3,9,17,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle t=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,22,0,14,3,2,19,4,15,1,21,3,6,6,3,21,1,15,4,19,2,3,14,0)$

Using the method in Section 5, the program computed the solution
$(\tilde{s},\tilde{t})$ to the DPD, where

$\displaystyle\tilde{s}=$
$\displaystyle(13,16,5,1,21,1,2,8,17,2,12,11,4,0,20,7,19,16,3,14,22,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle\tilde{t}=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,2,17,16,12,16,12,10,6,8,3,0,0,3,8,6,10,12,16,12,16,17,2)$

It was verified that $sht=\tilde{s}h\tilde{t}$, so a legitimate private key
was recovered.

######  Example 2.

For parameters $n=19,\ q=19$, $\lambda=18$, and using the notations above,
consider the randomly generated public element $h$, and secret key
$(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$.

$\displaystyle h=$
$\displaystyle(14,5,13,4,10,12,8,6,17,18,15,1,14,14,15,15,13,4,6,7,7,11,13,4,11,12,3,11,18,8,3,3,6,11,17,1,7,10),$
$\displaystyle s=$
$\displaystyle(18,14,1,0,15,5,7,0,1,7,10,5,9,18,2,12,17,12,14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle t=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,17,4,10,18,5,5,9,15,18,18,15,9,5,5,18,10,4,17)$

Using the method in Section 5, the program computed the solution
$(\tilde{s},\tilde{t})$ to the DPD, where

$\displaystyle\tilde{s}=$
$\displaystyle(12,6,4,10,12,4,5,7,0,15,8,7,1,0,2,15,6,7,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle\tilde{t}=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,13,11,10,3,3,1,1,3,16,16,3,1,1,3,3,10,11,13)$

It was verified that $sht=\tilde{s}h\tilde{t}$, so a legitimate private key
was recovered.

######  Example 3.

For parameters $n=41,\ q=41$, $\lambda=29$, and using the notations above,
consider the randomly generated public element $h$, and secret key
$(s,t)\in\mathbb{F}_{q}^{\alpha}C_{n}\times\Gamma_{\alpha}$.

$\displaystyle h=$
$\displaystyle(33,2,29,20,9,5,36,13,26,15,38,27,33,4,20,4,14,23,12,0,35,5,38,40,1,6,16,26,9,0,29,6,32,26,14,32,18,29,13,35,7,$
$\displaystyle
8,38,26,20,25,24,18,30,28,22,8,21,1,33,29,2,22,25,6,13,24,18,26,30,38,3,1,39,11,15,10,9,16,3,7,36,26,22,6,0,15),$
$\displaystyle s=$
$\displaystyle(24,2,12,32,10,2,27,1,5,7,17,32,7,24,28,26,17,8,32,18,13,8,19,17,0,11,33,17,27,1,36,3,33,9,30,34,$
$\displaystyle
22,26,21,5,29,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle t=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,13,8,18,11,31,$
$\displaystyle
9,34,3,16,39,32,0,15,31,3,26,0,31,39,4,40,40,4,39,31,0,26,3,31,15,0,32,39,16,3,34,9,31,11,18,8)$

Using the method in Section 5, the program computed the solution
$(\tilde{s},\tilde{t})$ to the DPD, where

$\displaystyle\tilde{s}=$
$\displaystyle(39,9,4,23,8,8,10,40,31,27,22,36,11,14,35,28,25,0,0,10,16,33,24,6,33,17,15,13,17,10,18,31,33,16,13,$
$\displaystyle
28,2,36,37,13,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$
$\displaystyle\tilde{t}=$
$\displaystyle(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,35,6,8,35,23,22,39,$
$\displaystyle
12,22,36,34,1,29,8,16,40,29,16,24,14,31,31,14,24,16,29,40,16,8,29,1,34,36,22,12,39,22,23,35,8,6)$

It was verified that $sht=\tilde{s}h\tilde{t}$, so a legitimate private key
was recovered.

Clearly, in each of the above examples, $s\neq\tilde{s}$ and $t\neq\tilde{t}$,
but $sht=\tilde{s}h\tilde{t}$. Thus, each of these examples also serves as a
counterexample to the injectivity of the two-sided action.

##  6 Conclusion

In this paper, we provided a method for cryptanalysis of the protocol in [4]
which is based on a double-sided multiplication problem in the twisted
dihedral group algebra $\mathbb{F}_{q}^{\alpha}D_{2n}$. We first showed that
the underlying DPD algorithmic problem is equivalent to a commutative
semigroup action problem. For our cryptanalysis, we showed that the task for
an adversary attempting to solve the underlying DPD problem is equivalent to
the solution of two equations in ${\mathbb{F}_{q}}$ involving circulant
matrices. We further demonstrated a polynomial time solution for these
equations using linear algebra, which works with a probability of
$1-(1-\frac{1}{q})^{2}$. For the proposed values of the parameters in [4],
this gives a success rate of at least 90 percent. The key exchange system in
[4] and its underlying algorithmic problem are both therefore clearly
insecure, even in a classical setting.

## References

  * [1] Adi Ben-Zvi, Arkadius Kalka, and Boaz Tsaban.  Cryptanalysis via algebraic spans.  In Annual International Cryptology Conference, pages 255–274. Springer, 2018.
  * [2] Ran Canetti and Hugo Krawczyk.  Analysis of key-exchange protocols and their use for building secure channels.  In Birgit Pfitzmann, editor, Advances in Cryptology — EUROCRYPT 2001, pages 453–474, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  * [3] Bren Cavallo and Delaram Kahrobaei.  A family of polycyclic groups over which the uniform conjugacy problem is np-complete.  International Journal of Algebra and Computation, 24(04):515–530, 2014.
  * [4] Javier de la Cruz and Ricardo Villanueva-Polanco.  Public key cryptography based on twisted dihedral group algebras.  Advances in Mathematics of Communications, 0:–, 2022.
  * [5] Javier De La Cruz and Wolfgang Willems.  Twisted group codes.  IEEE Transactions on Information Theory, 67(8):5178–5184, 2021\.
  * [6] Mohammad Eftekhari.  Cryptanalysis of some protocols using matrices over group rings.  pages 223–229, 04 2017.
  * [7] 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.
  * [8] María Dolores Gómez Olvera, Juan Antonio López Ramos, and Blas Torrecillas Jover.  Public key protocols over twisted dihedral group rings.  Symmetry, 11(8), 2019.
  * [9] Delaram Kahrobaei, Charalambos Koupparis, and Vladimir Shpilrain.  Public key exchange using matrices over group rings.  Groups - Complexity - Cryptology, 5(1):97–115, 2013.
  * [10] Juan Antonio López-Ramos, Joachim Rosenthal, Davide Schipani, and Reto Schnyder.  An application of group theory in confidential network communications.  Mathematical Methods in the Applied Sciences, 41:2294 – 2298, 2016\.
  * [11] 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.
  * [12] Alfred Menezes and Yihong Wu.  The discrete logarithm problem in $GL(n,q)$.  Ars Comb., 47, 1997.
  * [13] C. Monico.  Semirings and Semigroup Actions in Public-Key Cryptography.  PhD thesis, University of Notre Dame, May 2002.
  * [14] Alexei Myasnikov and Vitaliĭ Roman’kov.  A linear decomposition attack.  Groups Complexity Cryptology, 7(1):81–94, 2015.
  * [15] Alexey D. Myasnikov and Alexander Ushakov.  Quantum algorithm for discrete logarithm problem for matrices over finite group rings.  Groups Complexity Cryptology, 6(1):31–36, 2014.
  * [16] María-Dolores Olvera-Lobo, Juan Antonio López-Ramos, and Blas Torrecillas.  Public key protocols over twisted dihedral group rings.  Symmetry, 11:1019, 2019.
  * [17] Vitaly Roman’kov.  A general encryption scheme using two-sided multiplications with its cryptanalysis.  arXiv: Group Theory, 2017.
  * [18] Vitaly Roman’kov.  Two general schemes of algebraic cryptography.  Groups Complexity Cryptology, 10(2):83–98, 2018.
  * [19] Simona Samardjiska, Paolo Santini, Edoardo Persichetti, and Gustavo Banegas.  A reaction attack against cryptosystems based on lrpc codes.  In Peter Schwabe and Nicolas Thériault, editors, Progress in Cryptology – LATINCRYPT 2019, pages 197–216, Cham, 2019. Springer International Publishing.
  * [20] Peter W. Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), pages 124–134. IEEE Comput. Soc. Press, Los Alamitos, CA, 1994.
  * [21] Vladimir Shpilrain and Alexander Ushakov.  A new key exchange protocol based on the decomposition problem.  arXiv preprint arXiv:0512140, 2005.
  * [22] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 8.6), 2020.  https://www.sagemath.org.
  * [23] Simran Tinani, Carlo Matteotti, and Joachim Rosenthal.  Complexity of conjugacy search in some polycyclic and matrix groups, 2022\.
  * [24] Boaz Tsaban.  Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography.  Journal of Cryptology, 28(3):601–622, 2015.