Public key exchange protocols based on tropical lower circulant and anti circulant matrices

1.   Introduction

'Cryptography' is the process of establishing secure communication between the sender and the receiver of information ^[1,2]. The sender uses a method called 'encryption' to turn plaintext into a secret message called 'ciphertext', while the receiver uses a method called 'decryption' to convert the ciphertext back into plaintext ^[3,4]. A 'key' is secret common knowledge shared by both entities. There are two broad types of cryptography: symmetric key cryptography and asymmetric key cryptography. Symmetric key cryptography uses a single secret key for both encryption and decryption, which is only known by the sender and the receiver ^[5]. In asymmetric key cryptography, one key is used for encryption, and a different key is used for decryption ^[3,6]. Many varieties of cryptographic algorithms have been constructed over classical algebra ^[2]. Cryptographic algorithms over tropical algebra have gained significance in recent years, and tropical cryptography is one of the fields used to construct secure cryptographic algorithms. Martin Hellman and Whitfield Diffie suggested the two-keys cryptosystem in 1976 to overcome the issue of key distribution in symmetric key cryptography ^[4,7]. The general protocol that uses semi-direct products of semigroups was introduced in ^[8], and one of its special cases is the standard Diffie-Hellman protocol based on cyclic groups. This paper gives a conjecture that, when the protocol is used with non-commutative semigroups, it acquires several useful features. They suggest the extension of a particular non-commutative semigroup of matrices over a certain finite group ring by a conjugation automorphism as a suitable platform. However, the protocol introduced in ^[8] was attacked by the linear algebra attack ^[9]. The Cramer-Shoup scheme was introduced in ^[10] and proved to be secure against adaptive chosen ciphertext attacks. Stickel proposed the key exchange protocol based on classical algebra ^[11], which was then attacked by Shpilrain ^[12]. Grigoriev and Shpilrain extended Stickel's protocol by using tropical polynomials and showed that solving the system of tropical linear equations was NP-hard ^[13]. An advantage of using tropical algebras as the platform for building key exchange schemes is that, in tropical schemes, one does not have to perform any classical multiplication since tropical multiplication is classical addition and is not invertible ^[14,15,16]. However, the major weakness of the tropical protocol is that the tropical powers of the matrices exhibit a particular pattern, as noted by Kotov and Ushakov. This pattern helps them to attack Grigoriev's key exchange protocol ^[17]. Grigoriev and Shpilrain's next key exchange protocol was based on semidirect product ^[18], but it had the weakness that the sequence ${(M, H)^{l}}$ is linearly ordered, which was found by Rudy and Monico ^[19]. Issac and Kahrobaei implemented the linear periodicity attack ^[20] to attack the same protocol that used semidirect product. These attacks showed that key exchange protocols with matrix powers over the tropical approach are easily attackable. Different attacks of various tropical key exchange protocols were consolidated in ^[6]. The significance of our research is that our protocols are related to the tropical two sided matrix action problem that can be reduced to a system of non-linear equations, and solving such a system is NP-hard ^[13].

Our contribution: In this paper, we propose a key exchange protocol over the tropical semiring with min-plus operation. We avoid using power and linearly ordered operations over tropical concepts to ensure the safety of our schemes against popular attacks. We introduce the abelian subset $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, \oplus, \otimes)$ of the semiring $(M_{n \times n}(\mathfrak{Z}), \oplus, \otimes)$, which is obtained by modifying the set of $p$-circulant matrices and use it to frame our new protocol. Similarly, the protocol introduced in ^[21] uses the set of upper-$t$-circulant matrices, which is also obtained by modifying the set of circulant matrices. We provide a detailed analysis of the protocol using upper-$t$-circulant matrix ^[21] replaced by the protocol using lower-$s$-circulant matrix. We compare the protocols using the lower-$s$-circulant matrix instead of the upper-$t$-circulant matrix in the protocol introduced in ^[21] with our proposed protocol. We also provide some propositions on the commutativity of the set of lower-$s$-circulant matrices $(\mathfrak{C}_{l}(s))_{n}, \oplus, \otimes)$ and the commutative property of the set of anti-$s$-$p$-circulant matrices. We also give some propositions on the security of both protocols. We provide the security analysis of our proposed protocol against the existing tropical attacks of Kotov & Ushakov, Rudy & Monico.

The rest of the sections are organized as follows. In Section 2, we discuss some basic definitions and notations. Section 3 contains an analysis of key exchange protocol 1, which uses the lower-$s$-circulant matrix, the key generation scheme of protocol 1 with cryptographic algorithm, and an example. Similarly, in Section 4, we discuss our proposed key exchange protocol, the key generation scheme with the algorithm and an example. We also provide the security analysis of proposed protocol 2 in Section 4. Section 5 contains a comparative analysis of the protocol based on upper or lower-$s$-circulant matrices and our proposed protocol with the experimental results like time complexity, memory usage and possible attacks for both protocols.

2.   Preliminaries

Definition 1. ^[22] A non-empty set $S$ with two binary operations addition $(+)$ and multiplication $(\cdot)$ is called a semiring, if it satisfies the following axioms:

$1)$ $S$ is an abelian monoid under the operation addition with '0' as the unique identity element,

$2)$ $S$ is a monoid under the operation multiplication with a unique identity element denoted by '1',

$3)$ $u \cdot (v+w)$ is equal to $u\cdot v+u\cdot w$ and $(v+w)\cdot u$ is equal to $v\cdot u+w\cdot u$ $\forall$ $u, v, w\in S$,

$4)$ Both $u\cdot 0$ and $0\cdot u$ are equal to $0$ $\forall \; u \in S$,

$5)$ The identities under the two operations should not be the same element.

Example 2.1. The set $\mathbb{N}\cup \{0\}$ forms a semiring under the operations classical addition and classical multiplication where, $\mathbb{N}$ is the set of all natural numbers.

Definition 2. The following are the two tropical binary operations.

● $x\oplus y = max(x, y)$ (or) $x\oplus y = min(x, y)$.

● $x\odot y = x+y$.

Definition 3. ^[22] A set $R = S\cup\{\infty\}$ under the operations '$\oplus$' (tropical addition, (min)) and '$\otimes$' (tropical multiplication) is called a min-plus semiring if,

$1)$ $u\oplus v$ = $v \oplus u$ $\forall\; u, v\in R$,

$2)$ $(u\oplus v) \oplus w = u \oplus (v\oplus w)$ and $(u \otimes v) \otimes w = u \otimes (v \otimes w)$ $\forall \; u, v, w \in R$,

$3)$ $u \otimes (v\oplus w) = (u \otimes v) \oplus (u \otimes w)$ $\forall\; u, v, w \in R$,

$4)$ $\exists$ $e\in R$ $\forall$ $u \in R$ such that $e \oplus u = u \oplus e = u$ (Here, the additive identity is '$\infty$'),

$5)$ inverse does not exist.

Let $\mathbb{Z}$ denote the set of all integers and $\mathfrak{Z} = \mathbb{Z}\cup\{\infty\}$. In this paper, we have concentrated on the min-plus semiring $R = (\mathfrak{Z}, \oplus, \otimes)$.

We know that $(\mathfrak{Z}, \oplus, \otimes)$ is a commutative semiring with additive identity and multiplicative identity '$\infty$' and '$0$' respectively. Let $M_{n\times n}(\mathfrak{Z})$ denote the set of all $n\times n$ matrices over $\mathfrak{Z}$.

2.1.   Matrices over the min-plus semiring

The collection of all matrices over the semiring $S$ with '$m$' rows and '$n$' columns is denoted by $M_{m\times n}(R)$. Let $A \in M_{m\times n}(R)$. Every $ij^{th}$ element of $A$ is denoted by '$a_{ij}$'. Let $P = (p_{ij})\in M_{m\times n}(R)$, $Q = (q_{ij})\in M_{m\times n}(R)$, $T = (t_{ij})\in M_{n\times l}(R)$ and $\alpha \in R$.

In min-plus algebra ^[14,15,16] addition of two matrices is calculated by

and multiplication of two matrices is calculated by

where, $k \in \{1, 2, \cdots, n\}$

Example 2.2. The following is an example of tropical addition, tropical multiplication of two matrices and the tropical addition, tropical multiplication of a matrix.

Definition 4. A matrix $T\in M_{n\times n}(\mathfrak{Z})$ is said to be circulant ${C}_{n\times n}$ with entries $c_{1}, c_{2}, \cdots, c_{n}$ if it is of the form

Definition 5. A matrix $T\in M_{n\times n}(\mathfrak{Z})$ is said to be lower-$s$-circulant if the matrix is of the form

where $c_{1}, c_{2}, \cdots, c_{n}, s\in \mathfrak{Z}$. The set of all lower-$s$-circulant matrix of order '$n$' is denoted by $(\mathfrak{C}_{l}(s))_{n}$. Here, '$l$' denotes that the element '$s$' is added in all the 'lower diagonal' entries.

Example 2.3. An example of lower-$2$-circulant matrix is given below.

Then,

Proposition 2.4. If $A\in (\mathfrak{C}_{l}(s))_{n}$, $B\in (\mathfrak{C}_{l}(t))_{n}$ and $s\neq t$, then $A\otimes B \neq B\otimes A$.

Proof. Let $A\in (\mathfrak{C}_{l}(s))_{n}$ and $B\in (\mathfrak{C}_{l}(t))_{n}$

To prove the non-commutativity of $\mathfrak{C}_{l}(s)_{n}$ and $\mathfrak{C}_{l}(t)_{n}$, it is enough to prove that $(A\otimes B)_{ij}\neq (B\otimes A)_{ij}$ for some $1\leq i, j\leq n$.

Let us calculate the value of $(A \otimes B)_{11}$ and $(B \otimes A)_{11}$. We get,

Since $s\neq t$, we have $(A \otimes B)_{11}\neq (B \otimes A)_{11}$. Thus, $A\otimes B \neq B\otimes A$. □

Definition 6. A matrix $T\in M_{n\times n}(\mathfrak{Z})$ is said to be an anti-$s$-circulant $(\mathfrak{AC}^{u}_{l}(s))_{n}$ matrix with entries $c_{1}, c_{2}, \cdots, c_{n}, s$ if it is of the form

where $c_{1}, c_{2}, \cdots, c_{n}, s\in \mathfrak{Z}$ and set of all anti-$s$-circulant matrix of order '$n$' is denoted by $(\mathfrak{AC}^{u}_{l}(s))_{n}$. Here, '$l$' and '$u$' denote that '$s$' is added to both upper and lower anti-diagonals.

Definition 7. A matrix $T\in M_{n\times n}(\mathfrak{Z})$ is said to be an anti-$s$-$p$-circulant with entries $c_{1}, c_{2}, \cdots, c_{n}, s$ if it is of the form

where, $c_{k}-c_{k+1} = p$ $\forall$ $1\leq k\leq n$ and $p \in \mathbb{Z}$ and the set of all anti-$s$-$p$-circulant matrix of order '$n$' is denoted by $(\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$.

Example 2.5. An example of lower-$13$-circulant matrix and anti-$13$-circulant matrix of order 4 is given below.

The lower-$13$-circulant matrix of $\mathfrak{C}$ is,

The anti-$13$-circulant matrix of $\mathfrak{C}$ is,

An example of anti-$13$-$5$-circulant matrix is,

Proposition 2.6. If $A\in ((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, B\in ((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(t))_{n}$, then $A\otimes B \neq B \otimes A\; \forall \; s \neq t$.

Proof. Let $A\in ((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, B\in ((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(t))_{n}$

To prove the non-commutativity of the set $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$ and $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(t))_{n}$, it is enough to prove that $(A\otimes B)_{ij}\neq (B\otimes A)_{ij}$ for some $1\leq i, j\leq n$.

Let us compare $(A\otimes B)_{12}$ and $(B\otimes A)_{12}$,

since $s\neq t$, it implies $(A\otimes B)_{12}\neq(B\otimes A)_{12}$ and hence $A\otimes B\neq B\otimes A$. □

Proposition 2.7. $(\mathfrak{C}_{l}(s))_{n}$ (set of all lower-$s$-circulant matrices over $\mathfrak{Z}$) is a commutative tropical semiring and a subsemiring of $M_{n\times n}(\mathfrak{Z})$.

Proof. $1)$ To prove that $(\mathfrak{C}_{l}(s))_{n}$ is a subsemiring of $M_{n\times n}(\mathfrak{Z})$ it is enough to prove that it is closed under tropical addition and tropical multiplication. Let $A, B\in (\mathfrak{C}_{l}(s))_{n}$ with entries $a_{1}, a_{2}, \cdots, a_{n}, a_{1}+s, a_{2}+s, \cdots, a_{n}+s$ and $b_{1}, b_{2}, \cdots, b_{n}, b_{1}+s, b_{2}+s, \cdots, b_{n}+s$ respectively.

(a) Clearly $(\mathfrak{C}_{l}(s))_{n}$ is closed under tropical addition.

(b) Let the entry $(A\otimes B)_{ij}$ denotes the $ij^{th}$ entry of the matrix $A\otimes B$. $(C)_{k}$ and $(D)_{k}$, $1\leq k \leq n$ be the entries of circulant matrices to generate the lower-$s$-circulant matrices $A\otimes B$ and $B\otimes A$ respectively. Assume that $A, B\in (\mathfrak{C}_{l}(s))_{n}$. To prove that the set of all lower-$s$-circulant matrices are closed under the tropical multiplication, it is enough to prove that the matrix $A\otimes B$ is also in the following form

The diagonal entries of the tropical multiplication $A\otimes B$ of the matrices $A$ and $B$ are,

By rearranging the terms, it is clear that $(A \otimes B)_{kk}$ are equal for all $1\leq k\leq n$. In general, let us call these entries as $(C)_{1}$.

Now, the upper off diagonal entries are obtained as follows,

By rearranging the terms, we can see that the entries $(A\otimes B)_{(k-1)k}$ are equal for all $2\leq k\leq n$. We denote this value as $(C)_{n}$ in general

Then,

The next upper off diagonal elements are obtained as,

Again by rearranging the terms, it is clear that the entries $(A \otimes B)_{(k-2)k}$ are equal $\forall$ $3\leq k \leq n$. We name these entries as $(C)_{n-1}$ in general.

Then,

The entries $(A\otimes B)_{1(n-1)}, (A\otimes B)_{2n}$ are obtained as,

In general, we denote it as $(C)_{3}$. Then,

By continuing this process, finally we end up with the entry $(A\otimes B)_{1n}$. We name this entry as $(C)_{2}$

Similarly, we obtained the lower off diagonal elements with following values

By rearranging the above terms, we can see that $(A \otimes B)_{k(k-1)}$ are equal for all $2\leq k \leq n$. That is, $(A \otimes B)_{21} = (A \otimes B)_{32} = \cdots = (A \otimes B)_{n(n-1)}$

Now, the second lower off diagonal entries are obtained as,

Again, second lower off diagonal elements $(A \otimes B)_{k(k-2)}$ are equal for all $3 \leq k \leq n$. Which can be denoted as

Again by continuing this process, the final lower off diagonal entry is obtained as,

By placing all obtained elements in the following matrix of order $n$ we get the form of lower-$s$-circulant matrix

Hence, it is proved that the set of all lower-$s$-circulant matrix is closed under tropical multiplication.

$2)$ To show that $(\mathfrak{C}_{l}(s))_{n}$ is commutative, it is enough to show that $(C)_{k} = (D)_{k}$ and

$(C)_{k}+s = (D)_{k}+s$ for all $1\leq k\leq n$.

Since we found the entries of $A\otimes B$ in the previous proof, it is enough to find the entries of $B\otimes A$.

By rearranging the terms we get,

Similarly,

Also,

By continuing this process, we obtain the entry $(B \otimes A)_{n-1}$ as,

Finally, the term $(B \otimes A)_{n}$ is obtained as,

Now the next entry is obtained as,

Similarly,

Also,

And the final entry of $B\otimes A$ is obtained as,

Hence, it is proved that $(C)_{k} = (D)_{k}\; \forall\; 1\leq k\leq n$ and $(C)_{k}+s = (D)_{k}+s\; \forall\; 2\leq k\leq n$.

Thus,

□

Proposition 2.8. $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$ (set of all anti-$s$-$p$-circulant matrices) is a commutative subset of the tropical semiring $M_{n\times n}(\mathfrak{Z})$.

Proof.

To prove the commutativity of $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$, it is enough to prove that $(A\otimes B)_{ij} = (B\otimes A)_{ij}$, $\forall$ $1 \leq i, j \leq n$.

Let $A, B\in ((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$, then we have $a_{k_{1}}\otimes b_{k_{2}} = b_{k_{1}}\otimes a_{k_{2}} \forall\; 1\leq k_{1}, k_{2}\leq n$.

By using this property we get,

Similarly,

By continuing the process, we get,

Similarly, the entries of $(n)^{th}$ row of the matrix $A\otimes B$ is,

Thus,

□

3.   Public key exchange protocol 1

In this section, we discuss the protocol introduced in ^[21] with the help of lower-$s$-circulant matrices. Further we study the protocol which use upper or lower-$s$-circulant matrices to compare it with our proposed protocol that uses anti-$s$-$p$-circulant matrices $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}$.

3.1.   Description of the protocol 1

Step 1: Let $Y, s, t$ be the public parameters.

Step 2: Alice selects two matrices ${C_{1}}$ and $C_{2}$ and finds the two matrices $\mathfrak{A}_{1}, \mathfrak{B}_{1}.$

Step 3: Bob selects two matrices ${C_{3}}$ and $C_{4}$ and finds the two matrices $\mathfrak{A}_{2}, \mathfrak{B}_{2}.$

Step 4: Alice finds $K_{a} = \mathfrak{A}_{1}\otimes (Y) \otimes \mathfrak{B}_{1}$ and sends it to Bob.

Step 5: Bob finds $K_{b} = \mathfrak{A}_{2}\otimes (Y) \otimes \mathfrak{B}_{2}$ and sends it to Alice.

Step 6: Alice computes ${G_{1}} = \mathfrak{A}_{1}\otimes K_{b}\otimes \mathfrak{B}_{1}.$

Step 7: Bob computes ${G_{2}} = \mathfrak{A}_{2}\otimes K_{a}\otimes \mathfrak{B}_{2}.$

Step 8: By the properties of tropical algebra, the shared keys are the same. $K = {G_{1}} = {G_{2}}.$

3.2.   Key generation and parameters of protocol 1

● Let $Y, s, t$ be the public parameters, where the entries of $Y$ are the elements from the tropical semiring $(\mathbb{Z}\cup\{\infty\}, \oplus, \otimes)$. Similarly $s, t$ are integers.

● Alice selects two circulant matrices ${C_{1}}$ and $C_{2}$ from the tropical semiring $(M_{n}(\mathfrak{Z}), \oplus, \otimes)$ and finds the matrices $\mathfrak{A}_{1}, \mathfrak{B}_{1}$ with the use of $s, t$ where $\mathfrak{C}_{n}$ is set of all circulant matrices of order $n$.

● $(c_{1})^{1}, (c_{2})^{1}, (c_{3})^{1}, \cdots (c_{n})^{1}$ and $(c_{1})^{2}, (c_{2})^{2}, (c_{3})^{2}, \cdots (c_{n})^{2}$ are the elements of circulant matrices $C_{1}$ and $C_{2}$ respectively.

● Alice computes $K_{a} = \mathfrak{A}_{1}\otimes (Y) \otimes \mathfrak{B}_{1}.$

● Bob selects two circulant matrices ${C_{3}}$ and $C_{4}$ from the tropical semiring $(M_{n}(\mathfrak{Z}), \oplus, \otimes)$ and finds the matrices $\mathfrak{A}_{2}$ and $\mathfrak{B}_{2}$ with the help of $s, t.$

● $(c_{1})^{3}, (c_{2})^{3}, (c_{3})^{3}, \cdots (c_{n})^{3}$ and $(c_{1})^{4}, (c_{2})^{4}, (c_{3})^{4}, \cdots (c_{n})^{4}$ were the elements of circulant matrices $C_{3}$ and $C_{4}$ respectively.

● Bob computes $K_{b} = \mathfrak{A}_{2}\otimes (Y) \otimes \mathfrak{B}_{2}.$

● Alice finds the matrix

● Bob finds the matrix

● Finally, the shared keys are same $K = {G_{1}} = {G_{2}}$.

The proof is given in the following Proposition 3.2.

3.3.   A toy example

Example 3.1. Consider

Alice choose

and she finds

Bob choose

and he finds

Alice finds

Bob finds

Alice finds

Bob finds

Thus, the shared keys are equal $G_{1} = G_{2}.$

Suppose an attacker tries to find $\mathfrak{A}_{1}, \mathfrak{B}_{1}$ from the known matrices $K_{a}, Y, s, t$

Then, he will end up with the following tropical non-linear system,

$\min\{(-601)\otimes a_{0}\otimes b_{0}, 1182\otimes a_{0}\otimes b_{1}, 56129\otimes a_{0}\otimes b_{2}, 4325 \otimes a_{1}\otimes b_{0},$ $1862\otimes a_{1}\otimes b_{1}, 5029\otimes a_{1}\otimes b_{2}, (-554)\otimes a_{2}\otimes b_{0}, 1895\otimes a_{2}\otimes b_{1}, 1842\otimes a_{2}\otimes b_{2}\} = -1031$

$\min\{(-615)\otimes a_{0}\otimes b_{0}, 56129\otimes a_{0}\otimes b_{1}, (-601)\otimes a_{0}\otimes b_{2}, 65\otimes a_{1}\otimes b_{0},$ $5029\otimes a_{1}\otimes b_{1}, 4325\otimes a_{1}\otimes b_{2}, 98\otimes a_{2}\otimes b_{0}, 1842\otimes a_{2}\otimes b_{1}, (-554)\otimes a_{2}\otimes b_{2}\} = -1436$

$\min\{54332\otimes a_{0}\otimes b_{0}, (-601)\otimes a_{0}\otimes b_{1}, (-615)\otimes a_{0}\otimes b_{2}, 3232\otimes a_{1}\otimes b_{0},$ $4325\otimes a_{1}\otimes b_{1}, 65\otimes a_{1}\otimes b_{2}, 45\otimes a_{2}\otimes b_{0}, (-554)\otimes a_{2}\otimes b_{1}, 98\otimes a_{2}\otimes b_{2}\} = -1450$

$\min\{(-554)\otimes a_{0}\otimes b_{0}, 98\otimes a_{0}\otimes b_{1}+1842\otimes a_{0}\otimes b_{2}, (-755)\otimes a_{1}\otimes b_{0},$ $1028\otimes a_{1}\otimes b_{1}, 55975\otimes a_{1}\otimes b_{2}, 4325\otimes a_{2}\otimes b_{0}, 1862\otimes a_{2}\otimes b_{1}, 5029\otimes a_{2}\otimes b_{2}\} = -985$

$\min\{98\otimes a_{0}\otimes b_{0}, 1842\otimes a_{0}\otimes b_{1}, (-554)\otimes a_{0}\otimes b_{2}, (-769)\otimes a_{1}\otimes b_{0}, 55975\otimes a_{1}\otimes b_{1},$ $1042\otimes a_{1}\otimes b_{2}, (-89)\otimes a_{2}\otimes b_{0}, 55975\otimes a_{2}\otimes b_{1}, 4325\otimes a_{2}\otimes b_{2}\} = -1389$

$\min\{45\otimes a_{0}\otimes b_{0}, (-554)\otimes a_{0}\otimes b_{1}, 98\otimes a_{0}\otimes b_{2}, 54178\otimes a_{1}\otimes b_{0},$ $(-755)\otimes a_{1}\otimes b_{1}, (-769)\otimes a_{1}\otimes b_{2}+3232\otimes a_{2}\otimes b_{0}+4325\otimes a_{2}\otimes b_{1}+65\otimes a_{2}\otimes b_{2}\} = -1261$

$\min\{4325\otimes a_{0}\otimes b_{0}+1895\otimes a_{0}\otimes b_{1}+5029\otimes a_{0}\otimes b_{2}+(-708)\otimes a_{1}\otimes b_{0}+$ $1741\otimes a_{1}\otimes b_{1}, 1688\otimes a_{1}\otimes b_{2}, (-755)\otimes a_{2}b_{0}, 1028\otimes a_{2}\otimes b_{1}, 55975a_{2}b_{2}\} = -1052$

$\min\{65 \otimes a_{0}\otimes b_{0}, 5029 \otimes a_{0}\otimes b_{1}, 4325\otimes a_{0}\otimes b_{2}, (-56)\otimes a_{1}\otimes b_{0},$ $1688\otimes a_{1}\otimes b_{1}, (-708)\otimes a_{1}\otimes b_{2}, (-769)\otimes a_{2}\otimes b_{0}, 55975\otimes a_{2}\otimes b_{1}, (-755)\otimes a_{2}\otimes b_{2}\} = -1456$

$\min\{3232\otimes a_{0}\otimes b_{0}, 4325\otimes a_{0}\otimes b_{1}, 65\otimes a_{0}\otimes b_{2}, (-109)\otimes a_{1}\otimes b_{0},$ $(-708)\otimes a_{1}\otimes b_{1}, (-56)\otimes a_{1}\otimes b_{2}, 54486\otimes a_{2}\otimes b_{0}, (-755)\otimes a_{2}\otimes b_{1}, (-769)\otimes a_{2}\otimes b_{2}\} = -1470$

To attack the protocol, this system of non-linear equations has to be solved. But we already know that solving non-linear tropical equations is NP-Hard ^[13].

3.4.   Security analysis

The security of this protocol relies on the non-commutativity the lower-$s$-circulant matrix and the lower-$t$-circulant matrix.

Proposition 3.2. If $P_{1}\in (\mathfrak{C}_{l}(s))_{n}, Q_{1}\in (\mathfrak{C}_{l}(t))_{n}, P_{2}\in (\mathfrak{C}_{l}(s))_{n}, Q_{2}\in (\mathfrak{C}_{l}(t))_{n}$ and $s\neq t$, then

1) $P_{2}\otimes K_{a} \otimes Q_{2}$ = $P_{1}\otimes K_{b}\otimes Q_{1}$

2) $K_{a}\otimes K_{b}$ and $K_{b} \otimes K_{a}\neq P_{2}\otimes K_{a} \otimes Q_{2}$ and $P_{1}\otimes K_{b}\otimes Q_{1}$

where $K_{a} = (P_{1}\otimes Y \otimes Q_{1})$, $K_{b} = (P_{2}\otimes Y \otimes Q_{2})$.

Proof. $1)$ In this part of the proposition we prove that the shared secret keys are equal.

We know that by Proposition 2.7, $P_{1}\otimes P_{2} = P_{2}\otimes P_{1}$ and $P_{1}\otimes Q_{1}\neq Q_{1}\otimes P_{1}$.

Now, we consider,

Hence, we proved that the shared keys are equal.

2) In this part of the proposition, we show that an attacker cannot find the secret key with the known matrices $K_{a}, K_{b}$. Now, to prove the security of the protocol 1,

By Proposition 2.4

Hence, $K_{a}\otimes K_{b}$ and $K_{b} \otimes K_{a}\neq P_{2}\otimes K_{a} \otimes Q_{2}$ and $P_{1}\otimes K_{b}\otimes Q_{1}$

□

The time complexity of solving a tropical Grobner basis ^[23] for a tropical non-linear system of equations with $n \times n$ matrices is known to be $O(2^{(2^n)})$ which is extremely larger than $O(n^3)$.

4.   Public key exchange protocol 2

In this section, we propose a new key exchange protocol based on the anti-$s$-$p$-circulant matrices. We have given the algorithm, example and the security analysis of the proposed protocol.

4.1.   Description of the protocol 2

Step 1: Let $Y, s, t, p$ be the public parameters.

Step 2: Alice selects two $p$-circulant matrices $C_{1}$ and $C_{2}$ and finds the two matrices ${P_{1}}, {Q_{1}}.$

Step 3: Bob selects two $p$-circulant matrices $C_{3}$ and $C_{4}$ and finds the two matrices ${P_{2}}, {Q_{2}}.$

Step 4: Alice finds $K_{a} = {P_{1}}\otimes (Y) \otimes {Q_{1}}$ and sends it to Bob.

Step 5: Bob finds $K_{b} = {P_{2}}\otimes (Y) \otimes {P_{2}}$ and sends it to Alice.

Step 6: Alice computes ${G_{1}} = ({P_{1}}\otimes (K_{b})\otimes {Q_{1}}).$

Step 7: Bob computes ${G_{2}} = ({P_{2}}\otimes (K_{a})\otimes {Q_{2}}).$

Step 8: Computed values of both keys are same $K = {G_{1}} = {G_{2}}$.

4.2.   Key generation and parameters of protocol 2

● Let $Y, s, t, p$ be the public parameters, where the entries of $Y$ are the elements from the tropical semiring $(\mathfrak{Z}, \oplus, \otimes)$. Similarly $s, t \in \mathbb{Z}$.

● Alice selects two $p$-circulant matrices $C_{1}$ and $C_{2}$ from the tropical semiring $(M_{n}(\mathfrak{Z}), \oplus, \otimes)$ and finds ${P_{1}}$, ${Q_{1}}$ are the anti-$s$-$p$-circulant and anti-$t$-$p$-circulant matrices with the use of $p$-circulant matrices $C_{1}$ and $C_{2}$ respectively.

● $(c_{1})^{1}, (c_{2})^{1}, (c_{3})^{1}, \cdots (c_{n})^{1}$ and $(c_{1})^{2}, (c_{2})^{2}, (c_{3})^{2}, \cdots (c_{n})^{2}$ are the elements of $p$-circulant matrices $C_{1}$ and $C_{2}$ respectively.

● Alice computes $K_{a} = P_{1}\otimes (Y) \otimes Q_{1}.$

● Bob selects two $p$-circulant matrices $C_{3}$ and $C_{4}$ from the tropical semiring $(M_{n}(\mathfrak{Z}), \oplus, \otimes)$. ${P_{2}}$, ${Q_{2}}$ are the anti-$s$-$p$-circulant and anti-$t$-$p$-circulant matrices with the use of $C_{3}$ and $C_{4}$ respectively.

● $(c_{0})^{3}, (c_{1})^{3}, (c_{2})^{3}, \cdots (c_{n-1})^{3}$ and $(c_{0})^{4}, (c_{1})^{4}, (c_{2})^{4}, \cdots (c_{n-1})^{4}$ are the elements of $C_{3}$ and $C_{4}$ respectively.

● Bob computes $K_{b} = P_{2}\otimes (Y) \otimes Q_{2}.$

● Alice finds the matrix

● Bob finds the matrix

● Finally, shared keys were same $K = {G_{1}} = {G_{2}}$.

The proof is given in the following Proposition 4.2.

4.3.   A toy example

Example 4.1. Consider

Alice choose

and finds

Bob choose

and finds

Alice finds

and sends to Bob.

Bob finds

and sends to Alice.

Alice finds

Bob finds

Shared keys ${G_{1}} = {G_{2}}$

To attack the protocol the attacker has to solve the following tropical non-linear system of equations.

$\min\{1188805\otimes a_{0}\otimes b_{0}, 65371\otimes a_{0}\otimes b_{1}, 32434472\otimes a_{0}\otimes b_{2}, 43444\otimes a_{1}\otimes b_{0},$ $1313310\otimes a_{1}\otimes b_{1}, 34442\otimes a_{1}\otimes b_{2}, 98828\otimes a_{2}\otimes b_{0}, 96554\otimes a_{2}\otimes b_{1}, 955472\otimes a_{2}\otimes b_{2}\} = -168593$

$\min\{-33505\otimes a_{0}\otimes b_{0}, 32533348\otimes a_{0}\otimes b_{1}, 1188805\otimes a_{0}\otimes b_{2}, 32455\otimes a_{1}\otimes b_{0},$ $133318\otimes a_{1}\otimes b_{1}, 43444\otimes a_{1}\otimes b_{2}, (-2322)\otimes a_{2}\otimes b_{0}, 1054348\otimes a_{2}\otimes b_{1}, 98828\otimes a_{2}\otimes b_{2}\} = -168597$

$\min\{32533348\otimes a_{0}\otimes b_{0}, 1089929\otimes a_{0}\otimes b_{1}, 65371\otimes a_{0}\otimes b_{2}, 133318\otimes a_{1}\otimes b_{0},$ $(-55432)\otimes a_{1}\otimes b_{1}, 131331\otimes a_{1}\otimes b_{2}, 1054348\otimes a_{2}\otimes b_{0}, (-48)\otimes a_{2}\otimes b_{1}, 96554\otimes a_{2}\otimes b_{2}\} = -146668$

$\min\{98899\otimes a_{0}\otimes b_{0}, 96625\otimes a_{0}\otimes b_{1}, 955543\otimes a_{0}\otimes b_{2}, 1188805\otimes a_{1}\otimes b_{0},$ $65371\otimes a_{1}\otimes b_{1}, 32434472\otimes a_{1}\otimes b_{2}, 43373\otimes a_{2}\otimes b_{0}, 131260\otimes a_{2}\otimes b_{1}, 34371\otimes a_{2}\otimes b_{2}\} = -168666$

$\min\{(-2251)\otimes a_{0}\otimes b_{0}, 1054419\otimes a_{0}\otimes b_{1}, 98899\otimes a_{0}\otimes b_{2}, (-33505)\otimes a_{1}\otimes b_{0},$ $32533348\otimes a_{1}\otimes b_{1}, 1188805\otimes a_{1}\otimes b_{2}, 32384\otimes a_{2}\otimes b_{0}, 133247\otimes a_{2}\otimes b_{1}, 43373\otimes a_{2}\otimes b_{2}\} = -168670$

$\min\{1054419\otimes a_{0}\otimes b_{0}, 23\otimes a_{0}\otimes b_{1}, 96625\otimes a_{0}\otimes b_{2}, 32533348\otimes a_{1}\otimes b_{0},$ $1089929\otimes a_{1}\otimes b_{1}, 65371\otimes a_{1}\otimes b_{2}, 133247\otimes a_{2}\otimes b_{0}, (-55503)\otimes a_{2}\otimes b_{1}, 131260\otimes a_{2}\otimes b_{2}\} = -146670$

$\min\{43373\otimes a_{0}\otimes b_{0}, 131260\otimes a_{0}\otimes b_{1}, 34371\otimes a_{0}\otimes b_{2}, 98828\otimes a_{1}\otimes b_{0},$ $96554\otimes a_{1}\otimes b_{1}, 955472\otimes a_{1}\otimes b_{2}, 1188876\otimes a_{2}\otimes b_{0}, 33434\otimes a_{2}\otimes b_{1}, 32434543\otimes a_{2}\otimes b_{2}\} = 168662$

$\min\{32384\otimes a_{0}\otimes b_{0}, 133247\otimes a_{0}\otimes b_{1}, 43373\otimes a_{0}\otimes b_{2}, (-2322)\otimes a_{1}\otimes b_{0},$ $1054348\otimes a_{1}\otimes b_{1}, 98828\otimes a_{1}\otimes b_{2}, (-33434) \otimes a_{2}\otimes b_{0}), 32533419\otimes a_{2}\otimes b_{1}, 1188876\otimes a_{2}\otimes b_{2} = -168666$

$\min\{133247\otimes a_{0}\otimes b_{0}, (-55503)\otimes a_{0}\otimes b_{1}, 131260\otimes a_{0}\otimes b_{2}, 1054348\otimes a_{1}\otimes b_{0},$ $(-48)\otimes a_{1}\otimes b_{1}, 96554\otimes a_{1}\otimes b_{2}, 32533419\otimes a_{2}\otimes b_{0}, 1090000\otimes a_{2}\otimes b_{1}, 65442\otimes a_{2}\otimes b_{2}\} = -146601$

Solving this system of non-linear equation is NP-Hard. Thus, this makes our protocol secure ^[13].

4.4.   Security analysis

The security of this protocol relies on the non-commutativity of anti-$s$-circulant matrix with anti-$t$-circulant matrix.

Theorem 4.2. If $P_{1}\in ((\mathfrak{A}(D_{p}[{C}])^{u}_{l})(s))_{n}, Q_{1}\in ((\mathfrak{A}(D_{p}[{C}])^{u}_{l})(t))_{n},$ $P_{2}\in ((\mathfrak{A}(D_{p}[{C}])^{u}_{l})(s))_{n}, Q_{2}\in((\mathfrak{A}(D_{p}[{C}])^{u}_{l})(t))_{n}$ then

1) $P_{2}\otimes K_{a} \otimes Q_{2}$ = $P_{1}\otimes K_{b}\otimes Q_{1}$

2) $K_{a}\otimes K_{b}$ and $K_{b} \otimes K_{a}\neq P_{2}\otimes K_{a} \otimes Q_{2}$ and $P_{1}\otimes K_{b}\otimes Q_{1}$

where $K_{a} = (P_{1}\otimes Y \otimes Q_{1})$, $K_{b} = (P_{2}\otimes Y \otimes Q_{2})$

Proof. $1)$ We know that by Proposition 2.8, $P_{1}\otimes P_{2} = P_{2}\otimes P_{1}$ and $P_{1}\otimes Q_{1}\neq Q_{1}\otimes P_{1}$.

Now we consider,

Hence the shared keys are equal.

2) Now to prove the security of the protocol 1

By Proposition 2.4, we have,

Hence,

By Proposition 2.4

Hence, we have,

□

The tropical Grobner basis algorithm which is one approach to solving tropical non-linear systems ^[23]. In the worst case, the time complexity of computing a tropical Grobner basis for a system of equations with n by n matrices is known to be $O(2^{(2^n)})$.

4.5.   Possible attacks

The following are some of the attacks that an adversary may try to attack the proposed key exchange protocol and we have given how our key exchange scheme is secure against those attacks.

4.5.1.   Brute force attack

The brute force attack is an attacking technique in which the man in the middle tries all possible values to find the key. Suppose the attacker tries to get the key $G = P_{1}\otimes P_{2} \otimes Y \otimes Q_{1}\otimes Q_{2}$ from the public matrix $Y$ and from the shared matrices $K_{a} = P_{1}\otimes (Y) \otimes Q_{1}, K_{b} = P_{2}\otimes (Y) \otimes Q_{2}$ guessing the secret parameters is very hard since there are infinite possibilities. Also, if he try to find the values of $P_{1}, Q_{1}$ and $P_{2}, Q_{2}$ from $K_{a}$ and $K_{b}$ respectively then the possibility of finding $P_{1}, Q_{1}$ and $P_{2}, Q_{2}$ are infinite since we have taken the entries from the tropical semiring $(\mathbb{Z}\cup\{\infty\}, \oplus, \otimes)$. Thus, we can conclude that protocol 2 is secure from brute force attack.

4.5.2.   Linear algebra attack

The linear algebra attack is a key recovery technique by which an adversary may try to use the linear algebraic properties to attack the cryptosystem. The attack of Sphilrain on the classical Stickel's key exchange protocol is based on the fact that the keys were generated using invertible matrices.

In protocol 2, since we deal with tropical algebra, the matrices which we use $((\mathfrak{A}(D_{p}[{C}])^{u}_{l})(s))_{n}$ are not generally invertible. Thus, it makes our protocol secure from linear algebra attacks.

4.5.3.   Kotov and Ushakov attack

The KU attack is based on the fact that the tropical matrices displays pattern in higher tropical power. And also tropical multiplication of tropical coefficient is actually the usual addition of the coefficient with all the entries of the matrix. This fact helped Kotov and Ushakov to find the matrix

which allowed them to find the private parameters.

In protocol 2, we have used commutative elements from the semiring and we have not taken tropical powers of any matrix that is the primary reason why Kotov and Ushakov attack ^[17] won't work on protocol 2. We know that any circulant matrix with entries $a_{0}, a_{1}, \cdots, a_{n-1}$ can be written as the form of $a_{0}I+a_{1}P+\cdots+a_{n-1}P^{n-1}$ in classical algebra, where $P = [0, 1, \cdots, 0; 0, 0, 1, \cdots, 0; \cdots; 1, 0, \cdots, 0]$. In protocol 2 public matrix $Y$ cannot be written as the polynomial format unlike the one in ^[13]. The private parameters $P_{1}, Q_{1}, P_{2}, Q_{2}$ are not a circulant matrix they are from the lower/upper circulant matrices and they cannot be represented by the shared matrices $P_{1}\otimes Y \otimes Q_{1}$ and $P_{2}\otimes Y \otimes Q_{2}$.

4.5.4.   Rudy and Monico attack

The public key exchange protocol based on semidirect product of max plus matrices discussed in Section 4 of article ^[18] is developed by Grigoriev and Shpilrain. Let $R = (M_{n\times n}(\mathbb{Z}), \oplus, \otimes)$ and Alice and Bob agree the public matrices $M, H \in R$. Final key of Alice is $(B \circ H^{m})\oplus A = B\oplus H^{m}\oplus(B\otimes H^{m})\oplus A$ equals to the key of Bob $(A \circ H^{n})\oplus B = A\oplus H^{n}\oplus (A\otimes H^{n})\oplus B$ ^[18]. Where $H^{m}$ and $H^{n}$ denoted the $m^{th}$ and $n^{th}$ tropical power of $H$ matrix respectively. This protocol is attacked by Rudy and Monico by the simple binary search attack ^[19]. The main idea of the simple binary search attack is to find the tropical power $m$ at which the tuple $(M, H)$ becomes $(A, H^{m})$ with the known $A$. But in protocol 2 we never use any tropical powers. Hence, Rudy and Monico attack is not valid in protocol 2.

5.   Comparative analysis

In this section, we have compared the experimental results of both protocol 1 and protocol 2 with some familiar tropical protocols. The following experiments were done in a computer with 11th Gen Intel(R) Core(TM) i5-11300H @ 3.10 GHz processor with 8 GB ram running on windows 11 with 64-bits operating system. The algorithms of the protocols are executed in maple 2018 software.

Note: In the Table 1, ✘ denotes that the scheme is attacked by the corresponding attack and ✔ denotes that the scheme is safe against the attack.

Most of the tropical protocols proposed in recent years involves the exponentiation of the tropical matrices. When we compare the time complexity of tropical power based algorithms with our proposed algorithm, we can see that the time complexity of those algorithms is higher than our algorithms. That is, $O(n^3) < O(n^{n+3})$ where, $n$ is the dimension of matrices involved in tropical powers.

The idea of using commuting matrices in tropical linear algebra on the Stickel's protocol instead of tropical powers and polynomials have already been examined in ^[24,25,26]. In many protocols they have used circulant matrices but, the main idea of our paper is to generate secret keys efficiently with the commutative subset $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, \oplus, \otimes)$ of tropical semiring $(M_{n \times n}(\mathfrak{Z}), \oplus, \otimes)$.

5.1.   Comparison of protocol based on upper or lower-$s$-circulant matrices and proposed protocol 2

The key exchange protocol 1 is based on upper or lower-$s$-circulant matrices which contains $2n$ elements in $\mathfrak{A}, \mathfrak{B}, \mathfrak{C}, \mathfrak{D}$ and the protocol 2 based on anti-$s$-$p$-circulant matrices $P_{1}, P_{2}, Q_{1}, Q_{2}$ which are performed with $2n$ elements. The time complexity of both protocols are same. From Figure 1 we can analyse the key generation time of protocol 1 and protocol 2.

Given data in Table 2 is plotted in Figure 1 above.

Memory usage: We have analysed memory usage of protocol based on upper or lower-$s$-circulant matrices and our proposed protocol 2. This shows that the memory usage of our proposed protocol 2 is better than the memory usage of protocol 1.

Experimental datas of memory usage given in Table 3 is plotted in Figure 2.

Time complexity of protocol based on upper or lower-$s$-circulant matrices: In the key exchange protocol 1, we have four public parameters $Y, s, t, n$. Here $Y, s, t$ are fixed and variable is $n$. Matrices $\mathfrak{A}_{1}, \mathfrak{A}_{2}, \mathfrak{B}_{1}, \mathfrak{B}_{2}$ each with $2n$ elements and tropical multiplication is performing four times in the protocol. Therefore, the total time complexity of multiplying five matrices in the tropical semiring $(\mathfrak{C}_{l}(s))_{n}$ with order $n$ is $O(n^3 \times 4) = O(n^3)$.

Time complexity of proposed protocol 2: In the key exchange protocol 2, we have four public parameters $Y, s, t, n$. Here $Y, s, t$ are fixed and variable is $n$. Matrices $P_{1}, P_{2}, Q_{1}, Q_{2}$ each with $2n$ elements and tropical multiplication is performing four times in the protocol. Therefore, the total time complexity of multiplying five matrices in the tropical semiring $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, \oplus, \otimes)$ with order $n$ is $O(n^3 \times 4) = O(n^3)$.

Both protocol 1 and protocol 2 have the same time complexity but the memory usage of protocol 2 is lesser than that of protocol 1. The reason is that the protocol 2 is generated by the use of commutative subset of $((\mathfrak{A}(D_{p}[\mathfrak{C}])^{u}_{l})(s))_{n}, \oplus, \otimes)$ of tropical semiring $(M_{n \times n}(\mathfrak{Z}), \oplus, \otimes)$. Let protocol 1 is performed with the lower-$s$-circulant matrices of order n and protocol 2 is performed with anti-$s$-$p$-circulant matrices of order $k$, where $k > n$ then, protocol 2 would be more efficient than protocol 1.

6.   Conclusions

In this paper, we have proposed the key exchange protocol by introducing the commutative set of anti-$s$-$p$-circulant matrices. Most of the protocols over tropical semirings were proposed based on the tropical powers of the matrices. Attacks on the tropical protocols are commonly based on the fact that they exhibit pattern in higher powers. Some of the popular attacks are linear periodicity attack, RM attack, KU attack, etc. To overcome these attacks, we have proposed our protocol which do not involve the exponentiation of tropical matrices. We have given further analysis of the protocol 1 and additionally we have proved some propositions. In the security analysis, we have proved that our proposed protocol is resistant against popular attacks of the existing tropical protocols. Comparative analysis of protocol 1 and our proposed protocol 2 is given. We can see that our proposed protocol performs better in terms of memory usage. In future, we may try to apply these protocols in the security of digital signature and identity authentication schemes. Also, our future work is to find the existence and uniqueness of the solution of tropical two sided matrix action problem.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the editor and reviewers for their valuable comments and suggestions, which greatly help us improve the presentation of this article. We thank the referees for their thoughtful reading of this manuscript and their feedback.

Conflict of interest

The authors declare no conflict of interest.