1 Introduction
Matrix power function (MPF) was first introduced in late 2000’s. This function proved to be useful for application in symmetric and asymmetric cryptography, since all actions are performed with small integers. This means that no additional co-processors have to be used to perform actions with large elements as opposed to RSA encryption or elliptic curves cryptography. Examples of these protocols can be found in Sakalauskas and Luksys (2012), Sakalauskas et al. (2008), Mihalkovich and Sakalauskas (2012), Sakalauskas and Mihalkovich (2014). The constructed protocols belong to non-commuting cryptography, which currently is of special interest to researchers. However, to our knowledge none of the protocols of this branch have been proven to be based on candidate one-way functions relying on NP-complete problems.
Formally, MPF can be defined as a function of matrix Q as a parameter and matrices $(X,Y)$ as function arguments parameters denoted by ${F_{Q}}(X,Y)$ and expressed by the formula
where E is a matrix representing the function value. In this paper we mainly focus on papers (Sakalauskas et al., 2008; Mihalkovich and Sakalauskas, 2012; Sakalauskas et al., 2017) and (Liu et al., 2016). In the latter paper authors present an attack based on linear algebra, which can be applied to protocols, presented in Sakalauskas et al. (2008) and Mihalkovich and Sakalauskas (2012) to break them in polynomial time. Our aim is to prove that the latest version of the so-called matrix power asymmetric cipher (MPAC), presented in Sakalauskas et al. (2017), is resistant to the declared attack, thus repairing the flaw found. Also, due to provable security of the latest version of MPAC protocol, we are making a conjecture that the recovery of decryption key is a hard problem.
2 Our Previous Work
Let us consider a commutative multiplicative semigroup $\boldsymbol{S}$ of multiplicative order t. Hence the powers of elements of $\boldsymbol{S}$ can be defined in a commutative numeric ring ${\boldsymbol{Z}_{t}}$, where addition and multiplication are defined modulo t. Previously in Sakalauskas et al. (2017) we defined this group as Sylow subgroup ${\boldsymbol{\Gamma }_{p,n}}\subset {\boldsymbol{Z}_{n}}$ of prime multiplicative order p combined with an ideal ${\boldsymbol{J}_{p,n}}$ given by ${\boldsymbol{J}_{p,n}}=j{\boldsymbol{\Gamma }_{p,n}}$, where j is an idempotent of the semigroup ${\boldsymbol{Z}_{p}}$. Due to prime multiplicative order p of the platform semigroup ${\boldsymbol{\Gamma }_{p,n}^{\mathrm{\sharp }}}={\boldsymbol{\Gamma }_{p,n}}\cup {\boldsymbol{J}_{p,n}}$, all the powers of elements of this algebraic structure are contained in a power field ${\boldsymbol{Z}_{p}}$.
We construct a semigroup of square $m\times m$ matrices with entries defined in semigroup ${\boldsymbol{\Gamma }_{p,n}}$ and denote it by ${\boldsymbol{M}_{{\boldsymbol{\Gamma }_{p,n}}}}$. Analogously we construct a ring of square $m\times m$ matrices ${\boldsymbol{M}_{{\boldsymbol{Z}_{n}}}}$ with entries of these matrices defined in numerical field ${\boldsymbol{Z}_{p}}$.
The two-sided MPF (or MPF for short) for a fixed parameter matrix ${\boldsymbol{M}_{{\boldsymbol{\Gamma }_{p,n}}}}$ is denoted as follows:
where matrices $X=\{{x_{ij}}\}$ and $Y=\{{y_{ij}}\}$ are defined in a power ring ${\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$ and matrix $Q=\{{q_{ij}}\}$ is defined in a platform semigroup ${\boldsymbol{M}_{{\boldsymbol{\Gamma }_{p,n}}}}$. The entries of matrix $e=\{{e_{ij}}\}$ are calculated in the following way:
We will refer to matrices X and Y as matrix powers or power matrices, Q as a base matrix and E as a matrix power value.
The following main properties of MPF were presented and proven in Sakalauskas and Luksys (2012):
The idea of using MPF to perform asymmetric key exchange was initially proposed in Sakalauskas et al. (2008). The suggested protocol resembles a famous approach of Diffie and Hellman (1976).
According to the initial idea, two protocol parties, called Alice and Bob, agree on the public platform semigroup ${\boldsymbol{Z}_{p}}$ hence implying the power ring ${\boldsymbol{Z}_{p-1}}$. Both parties also agree on two sets of commuting matrices $\langle L\rangle \subset {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$ and $\langle R\rangle \subset {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$ generated by matrices L and R respectively. Furthermore the base matrix $Q\in {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$ is generated and published online.
To perform asymmetric key exchange Alice and Bob select their private keys – pairs of matrices $X\in \langle L\rangle ,Y\in \langle R\rangle $ for Alice and $U\in \langle L\rangle ,V\in \langle R\rangle $ for Bob. Their public keys are obtained using MPF, i.e. $A{=^{X}}{Q^{Y}}$ for Alice and $B{=^{U}}{Q^{V}}$ for Bob. Hence we have:
\[\begin{array}{l}\displaystyle {\mathit{PrK}_{A}}=(X,Y),\hspace{2em}{\mathit{PuK}_{A}}=A,\\ {} \displaystyle {\mathit{PrK}_{B}}=(U,V),\hspace{2em}{\mathit{PuK}_{B}}=B,\end{array}\]
where $\mathit{PrK}$ and $\mathit{PuK}$ denote private and public key respectively.Upon exchanging their public keys, Alice and Bob can agree on a common key K calculated as follows:
since matrices X, U and Y, V commute.
However, it is shown in Liu et al. (2016), that this asymmetric key exchange is vulnerable to a certain linear algebra attack. Furthermore, their idea also holds in case of asymmetric encryption proposed in Mihalkovich and Sakalauskas (2012).
We now recall an improved version of MPAC presented in Sakalauskas et al. (2017).
Alice and Bob agree on the public platform semigroup ${\boldsymbol{\Gamma }_{p,n}^{\mathrm{\sharp }}}$ hence implying the power field ${\boldsymbol{Z}_{p}}$. Furthermore, the base matrix $Q\in {\boldsymbol{M}_{{\boldsymbol{\Gamma }_{p,n}}}}$, as well as two non-commuting power matrices ${Z_{1}},{Z_{2}}\in {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$, are generated and published publicly for both parties to use.
To perform MPAC protocol Alice generates her private and public data using the following steps:
Hence Alice obtained her data: a private key $Pr{K_{A}}=(X,u({x_{1}},{x_{2}}))$, which she keeps a secret, and a public key ${\mathit{PuK}_{A}}=({A_{1}},{A_{2}},E)$, which is certificated and published online.
-
• She randomly selects non-singular secret matrix $X\in {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$;
-
• Alice selects a random function $u({x_{1}},{x_{2}})$, where variables are non-commuting and coefficients are in ${\boldsymbol{Z}_{p}}$. Using this function Alice calculates matrix $U=u({Z_{1}},{Z_{2}})$;
-
• She computes matrices $X{Z_{1}}{X^{-1}}={A_{1}}$, $X{Z_{2}}{X^{-1}}={A_{2}}$, ${^{X}}{Q^{U}}=E$.
To encrypt a secret message M Bob takes Alice’s public key ${\mathit{PuK}_{A}}$ and performs the following actions:
-
1. Bob chooses randomly a non-singular matrix $Y\in {\boldsymbol{M}_{{\boldsymbol{Z}_{p}}}}$;
-
2. He selects a random function $v({x_{1}},{x_{2}})$, where variables are non-commuting and coefficients are in ${\boldsymbol{Z}_{p}}$. Using this function he calculates matrix $V=v({Z_{1}},{Z_{2}})$. Then Bob takes matrices ${A_{1}}$ and ${A_{2}}$ and computes a matrix $W=v({A_{1}},{A_{2}})=Xv({Z_{1}},{Z_{2}}){X^{-1}}=XV{X^{-1}}$;
-
3. He raises matrix ${^{X}}{Q^{U}}$ to the obtained power matrix W on the left and obtains ${^{XV}}{Q^{U}}$ since $WX=XV$;
-
4. He raises the result matrix to the power matrix Y on the right and obtains ${^{XV}}{Q^{UY}}$ = K, which can then be converted to a bit string;
-
5. Bob computes the ciphertext C = $K\oplus M$, where ⊕ is bitwise sum modulo 2 of all entries of bit stings K and M;
-
6. Bob computes three matrices $({Y^{-1}}{Z_{1}}Y={B_{1}}$, ${Y^{-1}}{Z_{2}}Y={B_{2}}$, ${^{V}}{Q^{Y}}=F)$ which we denote by encryptor ε and sends it to Alice together with C.
Upon receiving the encryptor ε Alice performs the following actions to decrypt Bob’s message:
-
1. She uses matrices ${B_{1}}$ and ${B_{2}}$ and her secret function $u({x_{1}},{x_{2}})$ to compute $u({B_{1}},{B_{2}})={Y^{-1}}UY$;
-
2. Alice raises matrix ${^{V}}{Q^{Y}}$ to the power ${Y^{-1}}UY$ on the right and then raises the result matrix to the power X on the left and hence obtains a matrix $K={^{XV}}{Q^{UY}}$ and converts it to a bitstring;
The essential modification of the protocol suggested in Mihalkovich and Sakalauskas (2012) is an extra matrix ${Z_{2}}$, which is published as a public parameter. In the next section we will show that this improvement of the initial protocol is enough to protect secret key from linear algebra cryptanalysis.
3 The Analysis Linear Algebra Attack
Let us briefly recall the attack presented in Liu et al. (2016).
To break the asymmetric key exchange proposed in Sakalauskas et al. (2008) an attacker has to solve the following system of equations:
where matrices Q, L, R, A are publicly known. Using convenient discrete logarithm function this system can be transformed to the following system:
The latter system can be solved in polynomial time if at least one of matrices X, Y has an inverse. The algorithm for solving system (6) uses Kronecker product of matrices and stacking matrices X, Y into one long vector. Hence an extra restriction on private matrices has to be added. Namely, matrices X, Y, U, V have to be singular.
(6)
\[ \left\{\begin{array}{l}(l{d_{g}}Q)Y={X^{-1}}l{d_{g}}A,\\ {} {X^{-1}}L=L{X^{-1}},\\ {} YR=RY.\end{array}\right.\]Another way to avoid revealing of private keys in protocol (Sakalauskas et al., 2008) is to escape the discrete logarithm transformation of system (5). Hence the choice of the platform semigroup is vital to keep the protocol secure. As of now the platform group ${\boldsymbol{\Gamma }_{p,n}^{\mathrm{\sharp }}}$ seems to be a safe choice to avoid linear algebra attack since, in general, there is no common generator of this semigroup, nor is this semigroup isomorphic to the Cartesian or free product of several cyclic semigroups. For more information on this semigroup the reader can turn to Sakalauskas et al. (2017), where the security of MPAC is considered.
In their paper (Liu et al., 2016) have also suggested an idea of using non-commuting (semi)group to define a platform structure, i.e. the entries of base matrix Q should not commute. While this idea is interesting, it has to be thoroughly studied.
Furthermore, in Mihalkovich and Sakalauskas (2012) we presented an asymmetric encryption protocol, which unfortunately is not resistant to linear algebra attack described in Liu et al. (2016). The key-point of this attack is eliminating matrix U by replacing it with its polynomial expression. Hence the following system of equations has to be solved:
The authors of the attack have shown that this can be done in polynomial time.
However, in Sakalauskas and Mihalkovich (2014) and Sakalauskas et al. (2017) we have improved our protocol by choosing a safer platform semigroup and adding an extra public parameter, namely a power matrix ${Z_{2}}$. The latter improvement is useful since the matrix U can now be calculated using an abstract random function $u({x_{1}},{x_{2}})$. This comes from the structure of public data, namely matrices ${A_{1}}$, ${A_{2}}$, ${B_{1}}$, ${B_{2}}$ of both parties of the protocol, since
\[\begin{array}{l}\displaystyle X{Z_{1}}{X^{-1}}={A_{1}},X{Z_{2}}{X^{-1}}={A_{2}},\\ {} \displaystyle {Y^{-1}}{Z_{1}}Y={B_{1}},{Y^{-1}}{Z_{2}}Y={B_{2}}\end{array}\]
and hence
\[\begin{array}{l}\displaystyle u({B_{1}},{B_{2}})={Y^{-1}}u({Z_{1}},{Z_{2}})Y={Y^{-1}}UY,\\ {} \displaystyle v({A_{1}},{A_{2}})=Xv({Z_{1}},{Z_{2}}){X^{-1}}=XV{X^{-1}}\end{array}\]
regardless of functions $u({x_{1}},{x_{2}})$ and $v({x_{1}},{x_{2}})$ respectively. An important moment here is the arbitrary structure of these private functions, i.e. these functions can be obtained using any combination of additions and multiplications of scalar non-commuting variables ${x_{1}}$, ${x_{2}}$. For more clarity let us present several examples of these functions:
\[ {x_{1}}{x_{2}}+2{x_{2}}{x_{1}};\hspace{2.5pt}3{x_{1}}{x_{2}}{x_{1}}+{x_{1}}+2{x_{2}}+{x_{2}}{x_{1}};\hspace{2.5pt}\big({x_{1}^{2}}+3{x_{1}}+2\big)\big({x_{2}^{3}}-2{x_{2}^{2}}-1\big).\]
As we can see the exact expressions of private functions are limited only by imagination of Alice and Bob and play no part in the execution of the MPAC protocol. However, on the attacker’s side this unknown structure of private functions is an obstacle, which keeps him from eliminating matrix U. Furthermore, the length of coefficients vector in now unbounded since the space of all possible private functions is infinite, i.e. functions like ${x_{1}}{x_{2}}{x_{1}},{x_{2}}{x_{1}}{x_{2}},{x_{1}}{x_{2}^{2}}{x_{1}^{3}}{x_{2}^{4}}{x_{1}}$ as well as their combinations are a legitimate choice.Note that the suggestion of using singular matrices X, Y, U, V as private key is not valid in case of MPAC protocol due to conjugation constrains, i.e. matrices X and Y have to be invertible. Hence the security of MPAC protocol now relies on the correct choice of platform semigroup and the unknown structure of the private functions $u({x_{1}},{x_{2}})$ and $v({x_{1}},{x_{2}})$ respectively.
4 Conclusions
In our paper we presented an analysis of a certain attack suggested in Liu et al. (2016). While avoidance of this attack for asymmetric key exchange was suggested by authors themselves, the case of asymmetric encryption is more complicated. The essence of linear algebra attack on the early version of MPAC is elimination of the private matrix U due to its polynomial structure, which is publicly known.
We also analysed the resistance to this attack of improved version of Matrix Power Asymmetric Cipher (MPAC) suggested in Sakalauskas et al. (2017). Based on performed analysis we can see that the security of this protocol relies on the following facts:
-
• An attacker has to solve the so-called MPF problem with conjugation constraints;
-
• By choosing a platform semigroup ${\boldsymbol{\Gamma }_{p,n}^{\mathrm{\sharp }}}$ the transformation of MPF problem using discrete logarithm function can be avoided;
-
• By adding an extra matrix ${Z_{2}}$ as a public parameter matrices U and V can be calculated using arbitrary random functions. The space of these functions is unbounded.
So far we do not know the methods of the solution of systems defined by initial MPF equations, since they are not custom systems of algebraic equations. It is rather a system of power equations, where unknown variables are the powers of certain elements in semigroup. Furthermore, the unknown structure of private function is an extra factor, which has to be considered as well.
