EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
2025, Vol. 18, Issue 3, Article Number 5888
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

A Key Exchange Protocol Based on the Twin
Conjugacy Search Problem Over Tropical Algebra

Kashifa Begum A.1, V. Muthukumaran1, V. Govindan2, Haewon Byeon3,∗

1 Department of Mathematics, College of Engineering and Technology,
Faculty of Engineering and Technology, SRM Institute of Science and Technology, Kattanku-
lathur - 603203, Chengalpattu, Tamil Nadu, India
2 Department of Mathematics, Hindustan Institute of Technology and Science,
Chennai - 603103, Tamil Nadu, India
3 Convergence Department, Korea University of Technology and Education, Cheonan,
South Korea

Abstract. In public key cryptography, the security of the data leans on the hardness of solv-
ing some mathematical problems over algebraic structures, such as groups, rings, etc. The first
published key exchange protocol is by Diffie and Hellman in 1976, whose security hinges on the
challenges in solving the Discrete Logarithm Problem (DLP) over any finite field. In this research
article, we present a key exchange protocol based on the Twin Conjugacy Search Problem (TCSP),
a variant of the well-known Conjugacy Search Problem (CSP), and Tropical Algebra as a platform
for the TCSP. We have provided two variants of the key exchange protocol and also provided a
toy example. The chosen platform, Tropical Algebra, is a new approach and is easy to implement
and not computationally hard as with other non-abelian groups as a platform, since one doesn’t
have to perform any complex multiplication or addition. The security and complexity analysis of
the protocol have also been explored.

2020 Mathematics Subject Classifications: 14G50, 14T10, 15A80, 15B33

Key Words and Phrases: Conjugacy Search Problem, Twin Conjugacy Search Problem, Trop-
ical Algebra, Public Key Exchange

1. Introduction

In the zone of modern cryptography, the security of information, its transmission and
storage is predominant. The ability to shield sensitive data in an age of immanent digital
communication and interconnected systems is a primitive concern. Cryptographic algo-
rithms serve as the cutting edge in this venture, with one of the main stay being the

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v18i3.5888

Email addresses: kb5928@srmist.edu.in (Kashifa Begum A.),
muthu.v2404@gmail.com (V. Muthukumaran), govindoviya@gmail.com (V. Govindan),
bhwpuma@naver.com (Haewon Byeon)

https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0)



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 2 of 16

Discrete Logarithm Problem (DLP). The DLP has portrayed a core role in the develop-
ment of secure communication protocol, digital signatures, and public key cryptosystems.
Its resilience to attacks, at that time, formed the basis for the security of widely used
schemes, such as the Diffie–Hellman key exchange, ElGamal encryption, and the Digital
Signature Algorithm (DSA) [1–4].

The Discrete Logarithm Problem (DLP) for a group G is to find at least one
k ∈ G ∋, for given any two elements a, b ∈ G, b = ak.

One of the popular choices of G for the DLP are cyclic groups Z∗
p, where p is any prime.

The recent advancements and evolution towards quantum computing made it easy to
solve the DLP. Hence the search for a new hard problem for key exchange protocols led
us to the Conjugacy Search Problem (CSP), one of the flair generalizations of the DLP.
The combination of the DLP and CSP is given in [5].

The Conjugacy Decision Problem (CDP) for a group G is a decision making prob-
lem of determining, given any two elements a, b ∈ G, whether or not they are conjugate
in G, i.e., if ∃ an element g ∈ G ∋ g−1ag = b.

The Conjugacy Search Problem (CSP) for a group G requires us to search, for
any two given conjugate elements a, b ∈ G, a conjugating element g ∈ G ∋ g−1ag = b.

The (presumed) computational difficulty of this problem in some groups (namely in
braid groups, garside groups, non-commutative semi groups) has been used in several
group based public key protocols [6–8].

Though CSP on some particular platforms (the solutions to the CSP in polycyclic
groups, p-groups, and matrix groups are given in [9]) are vulnerable to security, they
still have the value of reference and the search for a suitable platform is an active area
of research. Despite that the CSP and its variant versions (namely, the Twin Conjugacy
Search Problem (TCSP) and the Double Conjugacy Search Problem (DCSP) [10, 11]) have
a sufficient security level and play a significant role on non-abelian group based public key
cryptography.

Nevertheless, the efficiency and security of cryptographic systems does not depend
only on the type of algorithm, but also on the choice of the platform. One such unprobed
platform is Tropical Algebra, a relatively recent branch of Mathematics which has emerged
as a cogent tool with applications extending over diverse fields, from Optimization, Com-
puter Science to Biology and Economics. The phrase Tropical was originated by French
Mathematicians in admiration of the Hungarian–born Brazilian Computer Scientist Imre
Simon. For introductory enlightenment on Tropical Geometry one can refer [12, 13].



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 3 of 16

The substance of Tropical Algebra lies in its competence to simplify complex problems
by rebuilding them into a more viable algebraic structure, by replacing the traditional
addition with the maximum (or minimum) operation and the traditional multiplication
with the traditional addition operation. For contemporary evolution in tropical algebra
one can refer [14–18].

Thus we have chosen Tropical Algebra as a platform for the TCSP based key exchange
protocol, and also elaborated on the resilience of the protocol to various attacks including
Brute Force attack and KU attack. The article is arranged as follows: In section 2, the
preliminaries required are given. The TCSP over tropical algebra is given in section 3.
The two versions of the protocol proposed is given in section 4. A toy example of the first
protocol is given in section 5. In section 6, the security and complexity analysis of the
protocol is given and the article is concluded in section 7.

2. Preliminaries

2.1. The Twin Conjugacy Search Problem

The TCSP is defined in [10] as follows:

The Twin Conjugacy Search Problem (TCSP) for a braid group Bn is to find
x1, x2 ∈ Bn, for given g,X1, X2 ∈ Bn,∋ X1 = x1gx

−1
1 , X2 = x2gx

−1
2 .

2.2. Chen and You’s Key Exchange Protocol

There are two versions of the key exchange protocol based on the TCSP over braid
group in [10] and we reiterate both the versions here.

Suppose that the two people who need to communicate are Alice and Bob.

Consider H : Bl+r → {0, 1}l(k), where H is a hash function, Bl+r is a braid group, and
l(k) is a security parameter. Let g ∈ Bl+r be a public element.

2.2.1. Protocol I

(i) Key Generation: Alice chooses two secret parameters x1, x2 ∈ LBl, and computes
Xi = xigx

−1
i , i = 1, 2. (X1, X2, g) is the public key and the private key is (x1, x2).

(ii) Encryption: Consider the cipher message m ∈ Bl+r, Bob selects a secret element
y ∈ RBr, and calculates Y = ygy−1, Zi = yXiy

−1, i = 1, 2, c = Enck(m), k =
H(Y, Z). The ciphertext is (Y, c).

(iii) Decryption: To Decrypt the ciphertext (Y, c), Alice compute Zi = xiY x−1
i , i =

1, 2, m = Deck(c), k = H(Y, Z).



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 4 of 16

2.2.2. Protocol II

(i) Key Generation: Alice chooses two secret parameters x1, x2 ∈ LBl, and computes
Xi = xigx

−1
i , i = 1, 2. The public key is (X1, X2, g) and the private key is (x1, x2).

(ii) Encryption: Bob selects two random parameters y1, y2 ∈ RBr, and calculates Yi =
yigy

−1
i , i = 1, 2. Bob also computes the secret keys Zij = yjXiy

−1
j , i = 1, 2, j = 1, 2.

The public key is (Y1, Y2, g) and the private key is (y1, y2).

(iii) Decryption: Alice computes the secret keys Zij = xiYjx
−1
i , i = 1, 2, j = 1, 2.

Because of ccs(Xi, Yj) = Zij = xiYjx
−1
i = yjXiy

−1
j , i = 1, 2, j = 1, 2, Alice and Bob

can calculate the same value through the hash function H:

k = H(ccs(X1, Y1), ccs(X1, Y2), ccs(X2, Y1), ccs(X2, Y2)).

2.3. Semiring

A semiring is a set R together with two binary operations ‘+’ and ‘·’ ∋

• (R,+) is a commutative monoid,

• (R, ·) is a monoid,

• Multiplication by 0 annihilates R, i.e., r · 0 = 0 · r = 0, ∀ r ∈ R, and

• Multiplication is both left and right distributive over addition, i.e.,

r · (s+ t) = (r · s) + (r · t)
(s+ t) · r = (s · r) + (t · r), ∀ r, s, t ∈ R.

2.4. Tropical Algebra

A tropical algebra is the semiring Rmin = (R ∪ {+∞},⊕,⊗), where the operations
⊕ and ⊗, referred to as tropical addition and tropical multiplication, respectively, are
defined as (∀ s, t ∈ R ∪ {+∞})

s⊕ t = min{s, t},
s⊗ t = s+ t.

2.5. Tropical Monomial

Let x = (x1, x2, . . . , xn) ∈ Rn
min, a ∈ R, and α = (α1, α2, . . . , αn) ∈ Zn . Then a

tropical monomial is the function

p(x) = a⊗ x⊗α1
1 ⊗ x⊗α2

2 ⊗ · · · ⊗ x⊗αn
n ,

where exponentiation is defined tropically as repeated tropical multiplication, i.e., x⊗αi
i =

αixi.

Ex. x1 ⊗ x2 ⊗ x2 = x1 ⊗ x⊗2
2 = x1 + 2x2.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 5 of 16

2.6. Inverse of a Tropical Monomial

Let p(x) be a tropical monomial over Rmin. We define the inverse of p(x) to be a
monomial p′(x) over Rmin ∋

p(x)⊗ p′(x) = 0.

Ex. If p(x) = a⊗ x⊗n, then p′(x) = −a⊗ (−x)⊗n, where a, x ∈ R and n ∈ N.

2.7. Tropical Matrix Algebra

2.7.1. Tropical Matrix

A matrix of order n × n with entries from tropical algebra Rmin equipped with tropical
addition ⊕ and multiplication ⊗ is called a tropical matrix.

The set of all n× n tropical matrices over Rmin is denoted by Mn(Rmin).

2.7.2. Tropical Diagonal Matrix

A tropical diagonal matrix is an n×n tropical matrix with entries ai ∈ R, i = 1, ..., n,
on the diagonal and ∞ elsewhere, that is,

D =


a1 ∞ . . . ∞
∞ a2 . . . ∞
...

...
. . .

...
∞ ∞ . . . an

.

2.7.3. Tropical Matrix Multiplication

Let P, Q ∈Mn(Rmin). Then T = P ⊗Q is given by

tij =
⊕n

k=1(pik ⊗ qkj).

Ex.

1 2 −1
3 1 3
2 −2 3

⊗
3 1 2
4 −1 3
2 1 −2

 =

1 0 −3
5 0 1
2 −3 1

.

2.7.4. Tropical Matrix Scalar Multiplication

Let P ∈Mn(Rmin) and s ∈ Rmin. Then the tropical matrix scalar multiplication s⊗ P is
given by

s⊗ P = (s⊗ E)⊗ P = s⊗ pij = s+ pij ,

where E is the multiplicative identity matrix.

Ex. 5 ⊗

1 2 −1
3 1 3
2 −2 3

 =

 5 ∞ ∞
∞ 5 ∞
∞ ∞ 5

⊗
1 2 −1
3 1 3
2 −2 3

 =

6 7 4
8 6 8
7 3 8

.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 6 of 16

2.7.5. Properties

The following are properties with respect to tropical matrix multiplication and scalar
multiplication. For all P,Q, S ∈Mn(Rmin), m, n ∈ Z and s, t ∈ Rmin,

• P ⊗ (Q⊗ S) = (P ⊗Q)⊗ S (Associativity)

• P⊗m ⊗ P⊗n = P⊗n ⊗ P⊗m = P⊗(m+n) (Commutativity)

• Multiplicative Identity Matrix:

∃ an unique n × n matrix E ∈ Mn(Rmin),∋ P ⊗ E = E ⊗ P = P , where

E =


0 ∞ . . . ∞
∞ 0 . . . ∞
...

...
. . .

...
∞ ∞ . . . 0

.

• Multiplicative Inverse Matrix:

Multiplicative inverse of a matrix P is a matrix P ′ ∈Mn(Rmin) ∋ P ⊗ P ′ = E.
In general, tropical matrices are non-invertible.

• Miscellaneous:

s⊗ P = P ⊗ s

(s⊗ P )⊗ (t⊗ P ) = (s⊗ t)⊕ (P ⊗ P ) = (s+ t)⊗ P⊗2

3. The Twin Conjugacy Search Problem over Tropical Algebra

In this section, the TCSP over tropical algebra is defined. The security and complexity
of the problem is also explored.

3.1. The Twin Conjugacy Search Problem over Tropical Algebra

The Twin Conjugacy Search Problem (TCSP) for the tropical algebra R =
Mn(Rmin) is to find two matrices A1, A2 ∈ R and two tropical monomials p1(x), p2(x)
over Rmin, for given (g(A), X1, X2) ∈ R × R × R, where g(x) is a tropical monomial and
A ∈ R,∋

X1 = p1(A1)⊗ g(A)⊗ p
′
1(A1),

X2 = p2(A2)⊗ g(A)⊗ p
′
2(A2).

3.2. Security of the Twin Conjugacy Search Problem

(i) Determinant Attack: The determinant attack is not valid because of the non
commutative property of determinants in tropical algebra. Even if an adversary
knows det(Xi) and det(g(A)), since pi(Ai), i = 1, 2 are unknowns, this attack is
invalid.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 7 of 16

(ii) Eigenvalue Attack: This attack may work in some classical group or ring, but we
have considered tropical algebra where finding the eigenvalues of a matrix is feeble.
Even if an adversary finds the eigenvalues of Xi and g(A), using it to find the secret
elements pi(Ai) is not effectual.

(iii) Cayley-Hamilton Attack: In [19], it is said that finding the value of a matrix
substituted in a polynomial is manageable if the matrix is known. Along with that
to use the Cayley-Hamilton attack, an adversary must know two polynomials ri over
Rmin ∋ ri(Ai) =

⊕n−1
k=1(ak ⊗Ak

i ), since Ai are unknown this attack is invalid.

3.3. Brute - Force Complexity

To find the secret keys pi(Ai), i = 1, 2, by Brute - Force Attack, is to find both pi and
Ai, i = 1, 2 or two n× n matrices Pi ∈ R ∋ Pi = pi(Ai), i = 1, 2. The time complexity of
finding an n× n matrix is O(n2).

Suppose that R is finite, i.e., we take R = Mn(Zηmin), then the exhaustive search
algorithm is given in Algorithm 1.

Algorithm 1 Exhaustive Search Algorithm

Input: X, g(A) ∈ R ∋ X = p(A1)⊗ g(A)⊗ p′(A1)
Output: Secret parameter p(A1) ∈ R
for i← 1 to η − 1 do

p̃(Ai)← pi(Ai)
for j ← 1 to η − 1 do

Xj = p̃(Ai)⊗ g(A)⊗ p̃′(Ai)
if X = Xj then

return Xj and pi(Ai)
end if

end for
end for

4. The Key Exchange Protocol based on the Twin Conjugacy Search
Problem over Tropical Algebra

We propose two key exchange protocols based on the TCSP over tropical algebra.

Assume Alice and Bob are the two parties who need to exchange information.

Consider the tropical algebra R = Mn(Rmin). Let H ⊂ R be the subset containing
all the tropical diagonal matrices. Let g(x) be a public tropical monomial over Rmin and
A ∈ R \H be public tropical matrix.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 8 of 16

4.1. The Key Exchange Protocol I

(i) Key Generation: Alice chooses two random secret tropical monomials p1(x), p2(x)
over Rmin, two secret matrices Di ∈ H, i = 1, 2 and sends (X1, X2) to Bob, where
X1 = p1(D1) ⊗ g(A) ⊗ p′1(D1) and X2 = p2(D2) ⊗ g(A) ⊗ p′2(D2). Thus the public
key is (X1, X2, g, A), and the private key is (p1, p2, D1, D2).

(ii) Encryption: Bob chooses a random secret tropical monomial q(x) over Rmin, a
secret matrix B ∈ H and sends Y to Alice, where Y = q(B) ⊗ g(A) ⊗ q′(B). Thus
the public key is (Y, g,A), and the private key is (q,B).

(iii) Decryption: Alice receives Y and computes Z1 = p1(D1) ⊗ Y ⊗ p′1(D1), Z2 =
p2(D2) ⊗ Y ⊗ p′2(D2). Bob receives (X1, X2) and computes Z̃1 = q(B) ⊗ X1 ⊗
q′(B), Z̃2 = q(B)⊗X2 ⊗ q′(B).

(iv) Correctness: Since pi(Di) ⊗ q(B) = q(B) ⊗ pi(Di), and p′i(Di) ⊗ q(B) = q(B) ⊗
p′i(Di), i = 1, 2, Alice and Bob have same secret key, that is, Zi = Z̃i, i = 1, 2.

Table 1: The Key Exchange Protocol I

Alice Bob

p1(x), p2(x)← Rmin, D1, D2 ← H
X1 = p1(D1)⊗ g(A)⊗ p′1(D1)
X2 = p2(D2)⊗ g(A)⊗ p′2(D2)

X1,X2−→
q(x)← Rmin, B ← H

Y = q(B)⊗ g(A)⊗ q′(B)
Y←−

Z1 = p1(D1)⊗ Y ⊗ p′1(D1) Z̃1 = q(B)⊗X1 ⊗ q′(B)

Z2 = p2(D2)⊗ Y ⊗ p′2(D2) Z̃2 = q(B)⊗X2 ⊗ q′(B)

Z1 = Z̃1

Z2 = Z̃2

4.2. The Key Exchange Protocol II

(i) Key Generation: Alice chooses two random secret tropical monomials p1(x), p2(x)
over Rmin, two secret matrices D1, D2 ∈ H and sends (X1, X2) to Bob, where X1 =
p1(D1) ⊗ g(A) ⊗ p′1(D1) and X2 = p2(D2) ⊗ g(A) ⊗ p′2(D2). Then the public key
is (X1, X2, g, A), while the private key is (p1, p2, D1, D2).

(ii) Encryption: Bob chooses two random secret tropical monomials q1(x), q2(x) over
Rmin, two secret matrices B1, B2 ∈ H and sends (Y1, Y2) to Alice, where Y1 =
q1(B1) ⊗ g(A) ⊗ q′1(B1) and Y2 = q2(B2) ⊗ g(A) ⊗ q′2(B2). Then the public key is
(Y1, Y2, g, A), while the private key is (q1, q2, B1, B2).



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 9 of 16

(iii) Decryption: Alice receives (Y1, Y2) and computes Zij = pi(Di)⊗Yj⊗ p′i(Di), i, j =
1, 2. Bob receives (X1, X2) and computes Z̃ij = qj(Bj)⊗Xi⊗ q′j(Bj), i = 1, 2, j =
1, 2.

(iv) Correctness: Since pi(Di) ⊗ qj(Bj) = qj(Bj) ⊗ pi(Di), and p′i(Di) ⊗ qj(Bj) =
qj(Bj) ⊗ p′i(Ai), i, j = 1, 2, Alice and Bob have same secret key, that is, Zij =
Z̃ij , i = 1, 2, j = 1, 2.

Table 2: The Key Exchange Protocol II

Alice Bob

p1(x), p2(x)← Rmin, D1, D2 ← H
X1 = p1(D1)⊗ g(A)⊗ p′1(D1)
X2 = p2(D2)⊗ g(A)⊗ p′2(D2)

X1,X2−→
q1(x), q2(x)← Rmin, B1, B2 ← H

Y1 = q1(B1)⊗ g(A)⊗ q′1(B1)
Y2 = q2(B2)⊗ g(A)⊗ q′2(B2)

Y1,Y2←−
Zij = pi(Di)⊗ Yj ⊗ p′i(Di) Z̃ij = qj(Bj)⊗Xi ⊗ q′j(Bj)

Zij = Z̃ij ,
i = 1, 2, j = 1, 2

5. A Toy Example of the Protocol

In this section, a toy example of the first protocol is given.

Let p1(x) = 2 ⊗ x⊗2, p2(x) = 5 ⊗ x⊗3, q(x) = 2 ⊗ x, D1 =

 2 ∞ ∞
∞ 3 ∞
∞ ∞ 6

 , D2 = 1 ∞ ∞
∞ −5 ∞
∞ ∞ 4

 , B =

 6 ∞ ∞
∞ 5 ∞
∞ ∞ −3

 be private.

Let g(x) = 3⊗ x⊗2 and A =

 1 2 −1
3 5 −2
−1 2 3

 be public.

Then p′1(x) = −2⊗ (−x)⊗2, p2(x) = −5⊗ (−x)⊗3, q(x) = −2⊗ (−x).

Alice calculates



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 10 of 16

p1(D1) = 2 ⊗

 2 ∞ ∞
∞ 3 ∞
∞ ∞ 6

⊗2

= 2 ⊗

 4 ∞ ∞
∞ 6 ∞
∞ ∞ 12

 =

 6 ∞ ∞
∞ 8 ∞
∞ ∞ 14

 ,

p′1(D1) = −2 ⊗

−2 ∞ ∞
∞ −3 ∞
∞ ∞ −6

⊗2

= −2 ⊗

−4 ∞ ∞
∞ −6 ∞
∞ ∞ −12

 =

−6 ∞ ∞
∞ −8 ∞
∞ ∞ −14

 ,

p2(D2) = 5 ⊗

 1 ∞ ∞
∞ −5 ∞
∞ ∞ 4

⊗3

= 5 ⊗

 3 ∞ ∞
∞ −15 ∞
∞ ∞ 12

 =

 8 ∞ ∞
∞ −10 ∞
∞ ∞ 17

 ,

p′2(D2) = −5 ⊗

−1 ∞ ∞
∞ 5 ∞
∞ ∞ −4

⊗3

= −5 ⊗

−3 ∞ ∞
∞ 15 ∞
∞ ∞ −12

 =

−8 ∞ ∞
∞ 10 ∞
∞ ∞ −17

 ,

g(A) = 3 ⊗

 1 2 −1
3 5 −2
−1 2 3

⊗2

= 3 ⊗

−2 1 0
−3 0 1
0 1 −2

 =

1 4 3
0 3 4
3 4 1

.

Also X1 =

 6 ∞ ∞
∞ 8 ∞
∞ ∞ 14

⊗
1 4 3
0 3 4
3 4 1

⊗
−6 ∞ ∞
∞ −8 ∞
∞ ∞ −14

 =

 1 2 −5
2 3 −2
11 10 1

 ,

X2 =

 8 ∞ ∞
∞ −10 ∞
∞ ∞ 17

⊗
1 4 3
0 3 4
3 4 1

⊗
−8 ∞ ∞
∞ 10 ∞
∞ ∞ −17

 =

 1 22 −6
−18 3 −23
12 31 1

.

Bob calculates

q(B) = 2 ⊗

 6 ∞ ∞
∞ 5 ∞
∞ ∞ −3

 =

 8 ∞ ∞
∞ 7 ∞
∞ ∞ −1

 ,

q′(B) = −2 ⊗

−6 ∞ ∞
∞ −5 ∞
∞ ∞ 3

 =

−8 ∞ ∞
∞ −7 ∞
∞ ∞ 1

 ,

g(A) = 3 ⊗

 1 2 −1
3 5 −2
−1 2 3

⊗2

= 3 ⊗

−2 1 0
−3 0 1
0 1 −2

 =

1 4 3
0 3 4
3 4 1

.

Also Y =

 8 ∞ ∞
∞ 7 ∞
∞ ∞ −1

⊗
1 4 3
0 3 4
3 4 1

⊗
−8 ∞ ∞
∞ −7 ∞
∞ ∞ 1

 =

 1 5 12
−1 3 12
−6 −4 1

.

Alice’s shared secret key

Z1 =

 6 ∞ ∞
∞ 8 ∞
∞ ∞ 14

⊗
 1 5 12
−1 3 12
−6 −4 1

⊗
−6 ∞ ∞
∞ −8 ∞
∞ ∞ −14

 =

1 3 4
1 3 6
2 2 1

 ,



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 11 of 16

Z2 =

 8 ∞ ∞
∞ −10 ∞
∞ ∞ 17

⊗
 1 5 12
−1 3 12
−6 −4 1

⊗
−8 ∞ ∞
∞ 10 ∞
∞ ∞ −17

 =

 1 23 3
−19 3 −15
3 23 1

.

Bob’s shared secret key

Z̃1 =

 8 ∞ ∞
∞ 7 ∞
∞ ∞ −1

⊗
 1 2 −5

2 3 −2
11 10 1

⊗
−8 ∞ ∞
∞ −7 ∞
∞ ∞ 1

 =

1 3 4
1 3 6
2 2 1

 ,

Z̃2 =

 8 ∞ ∞
∞ 7 ∞
∞ ∞ −1

⊗
 1 22 −6
−18 3 −23
12 31 1

⊗
−8 ∞ ∞
∞ −7 ∞
∞ ∞ 1

 =

 1 23 3
−19 3 −15
3 23 1

.

Thus Z1 = Z̃1 =

1 3 4
1 3 6
2 2 1

 and Z2 = Z̃2 =

 1 23 3
−19 3 −15
3 23 1

 .

6. Security and Complexity Analysis of the Protocol

6.1. Completeness of the Protocol

In this subsection, we prove the completeness of the proposed key exchange protocols.

Lemma 1. Tropical diagonal matrix multiplication is commutative.

Proof. Let D and E be two n × n tropical diagonal matrices ∈ H. We wish to prove
that D ⊗ E = E ⊗D.

(D ⊗ E)ij =

n⊕
j=1

(Dij ⊗ Eji)

= min
j

(Dij + Eji)

Since D and E are diagonal matrices, Dij =∞ for i ̸= j and Eji =∞ for i ̸= j. Therefore,
(D⊗E)ij =∞ for i ̸= j and the only non-infinite term in the product occurs when i = j.
Therefore,

(D ⊗ E)ii = min
i

(Dii + Eii)

Similarly, for the product matrix E ⊗D, we have

(E ⊗D)ij =
n⊕

j=1

(Eij ⊗Dji) = min
j

(Eij +Dji)

(E ⊗D)ii = min
i

(Eii +Dii)

Thus,

D ⊗ E = E ⊗D. □



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 12 of 16

Theorem 1. The protocols are complete, i.e., Zi = Z̃i, i = 1, 2 and Zij = Z̃ij , i =
1, 2, j = 1, 2.

Proof. To prove that Protocol I is complete, we need to prove that Zi = Z̃i, i = 1, 2.

Zi = pi(Di)⊗ Y ⊗ p′i(Di), i = 1, 2

= pi(Di)⊗ (q(B)⊗ g(A)⊗ q′(B))⊗ p′i(Di)

= (pi(Di)⊗ q(B))⊗ g(A)⊗ (q′(B)⊗ p′i(Di))

= (q(B)⊗ pi(Di))⊗ g(A)⊗ (p′i(Di)⊗ q′(B))

= q(B)⊗ (pi(Di)⊗ g(A)⊗ p′i(Di))⊗ q′(B)

= q(B)⊗Xi ⊗ q′(B)

= Z̃i, i = 1, 2.

To prove that Protocol II is complete, we need to prove that Zij = Z̃ij , i = 1, 2, j = 1, 2.

Zij = pi(Di)⊗ Yj ⊗ p′i(Di), i = 1, 2, j = 1, 2

= pi(Di)⊗ (qj(Bj)⊗ g(A)⊗ q′j(Bj))⊗ p′i(Di)

= (pi(Di)⊗ qj(Bj))⊗ g(A)⊗ (q′j(Bj)⊗ p′i(Di))

= qj(Bj)⊗ pi(Di)⊗ g(A)⊗ p′i(Di)⊗ q′j(Bj)

= qj(Bj)⊗ (pi(Di)⊗ g(A)⊗ p′i(Di))⊗ q′j(Bj)

= qj(Bj)⊗Xi ⊗ q′j(Bj)

= Z̃ij , i = 1, 2, j = 1, 2. □

6.2. Security Analysis

6.2.1. Linear Algebra Attack

In linear algebra attack, an adversary uses the algebraic properties to discover the secret
key. Since we have considered tropical algebra as a platform for our protocol, to find
exactly the secret matrices by this attack is not likely.

For the first protocol, to find the key Zi from Xi, one needs to know pi(Di), i = 1, 2,
or to find the key from Y , one needs to know q(B).

Similarly, for the protocol II, to find the key Zij from Xi, one needs to know pi(Di), i =
1, 2 or to find the key from Yj , one needs to know qj(Bj), j = 1, 2.

Since tropical addition and multiplication of matrices are not invertible, this attack is
not possible.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 13 of 16

6.2.2. Brute-Force Attack

In this attack, an adversary uses every possible matrix to obtain the secret matrices from
Xi, i = 1, 2 and g(A). As we have considered R = Mn(Rmin), an infinite number of
possible matrices are at hand, it becomes hard to get the desired matrix by this attack
for adequate size of the matrix. Also, the brute force complexity for finite R is discussed
in section 3.3. Thus this attack is not feasible.

6.2.3. Kotov-Ushakov Attack

In [19], the authors expressed that tropical power of matrices exhibit a specific pattern.
This attack is not possible, since in both the protocols powers of unknown matrices Di, i =
1, 2 and B,Bj , j = 1, 2 are used to generate the keys Zi and Zij , i = 1, 2, j = 1, 2.

6.2.4. Rudy-Monico Attack

This attack lies on the strength of finding the power of a known tropical matrix [20].
Since we have used powers of unknown matrices Di, i = 1, 2 and B,Bj , j = 1, 2 in our
protocols, this attack is not achievable.

6.3. Complexity Analysis

We bestow the number of bit operations required for the generation of the secret keys:

For the first protocol,

• The number of bit operations required to tropical multiply two n × n matrices is
O(n3).

• The number of bit operations required to tropical multiply a diagonal matrix and
usual non-diagonal matrix is O(n2).

• To find Xi, i = 1, 2 the number of bit operations required is n2 + n2, which is
proportional to O(n2).

• To find Y , the number of bit operations required is n2 + n2, which is proportional
to O(n2).

Hence to find the secret keys Zi, i = 1, 2, the number of bit operations required is O(n2).

Similarly, for the protocol II, the number of bit operations required to find the secret
keys Zij , i = 1, 2, j = 1, 2 is O(n2).



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 14 of 16

Table 3: Comparative Analysis I

Aspect Braid Group, Bn Tropical Matrix Algebra

Algebraic Structure Group Semiring

Commutativity Non-commutative Non-commutative

Generators σ1, σ2, . . . , σn−1 Mn(Rmin) is not finitely gen-
erated

Operations Composition of braids Tropical addition (min/max),
Tropical multiplication (addi-
tion)

Accessibility It isn’t widely accessible since
braid groups require deeper
understanding of group the-
ory

It is widely accessible since
tropical algebra relies on ba-
sic arithmetic.

Table 4: Comparative Analysis II

Aspect Chen et al. [10] Our Protocol

Algebraic Structure Braid Group Tropical Matrix
Algebra

Base Problem TCSP TCSP

Time Complexity For Braid Concatenation, O(n),
and for Braid Simplification,
O(n2)

O(n2)

6.4. Comparative Analysis

In this section, we have compared our chosen platform, tropical algebra, with another
algebraic structure, i.e., a Braid group.

While the braid group holds significant theoretical value and serves specialized ap-
plications, it remains conceptually and computationally complex, with relatively limited
practical accessibility. Tropical algebra, on the other hand, are quite computationally
and conceptually approachable, making them easily implementable and widely usable in
everyday applications.

Therefore, in terms of practical utility and accessibility, tropical algebra offer a clear
advantage, whereas braid groups are better suited to specialized, niche domains.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 15 of 16

7. Conclusion

The permanent increase in computational power requires us to search for new plat-
forms for existing protocols. Tropical algebra seems to be an ideal candidate. In this
article, we have delved into the intriguing realm of the Twin Conjugacy Search Problem
by employing the innovative framework of Tropical Algebra. The security and complex-
ity of the TCSP over tropical algebra have been explored. We showed that our our key
exchange protocols based on the TCSP over tropical algebra are secure against Linear
Algebra, Kotov-Ushakov, Rudy-Monico and Brute - Force Attack. The complexity of the
protocols along with a comparative analysis have also been described.

Acknowledgements

We sincerely appreciate the editors and anonymous reviewers for their insightful sug-
gestions, which greatly enhanced the quality of this paper.

Funding

This research Supported by Basic Science Research Program through the National Re-
search Foundation of Korea (NRF) funded by the Ministry of Education (NRF- RS-2023-
00237287, NRF-2021S1A5A8062526) and local government-university cooperation-based
regional innovation projects (2021RIS-003).

Declaration of competing interest: The author confirms the absence of any known
financial conflicts of interest or personal relationships that might have influenced the work
presented in this paper.

Author’s Contribution: All authors made equal contributions to the manuscript, par-
ticipated in its drafting and revision, and approved the final version.

References

[1] W Diffie and M Hellman. New directions in cryptography. IEEE Transactions on
Information Theory, 22(6):644–654, Nov 1976.

[2] T Elgamal. A public key cryptosystem and a signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory, 31(4):469–472, Jul 1985.

[3] Digital signature standard (dss). National Institute of Standards and Technology
(U.S.), 1994.

[4] Any Muanalifah and Sergĕı Sergeev. On the tropical discrete logarithm problem
and security of a protocol based on tropical semidirect product. Communications in
Algebra, 50(2):861–879, 2022.



Kashifa Begum A. et. al / Eur. J. Pure Appl. Math, 18 (3) (2025), 5888 16 of 16

[5] Neha Goel, Indivar Gupta, M. K. Dubey, and B. K. Dass. Undeniable signature
scheme based over group ring. Applicable Algebra in Engineering, Communication
and Computing, 27(6):523–535, Dec 2016.

[6] Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju sung Kang, and
Choonsik Park. New public-key cryptosystem using braid groups. Lecture Notes in
Computer Science, pages 166–183, 2000.

[7] Volker Gebhardt and Juan González-Meneses. Solving the conjugacy problem in
garside groups by cyclic sliding. Journal of Symbolic Computation, 45(6):629–656,
Jun 2010.

[8] Dima Grigoriev and Vladimir Shpilrain. Authentication from matrix conjugation.
Groups – Complexity – Cryptology, 1(2), Jan 2009.

[9] Simran Tinani, Carlo Matteotti, and Joachim Rosenthal. Solutions to the conjugacy
search problem in various platform groups. AWM Research Symposium, 2022.

[10] Xiaoming Chen, Weiqing You, and Li Wenxi. The twin conjugacy search problem
and applications, Jun 2018.

[11] V. Muthukumaran, M. Adhiyaman, and D. Ezhilmaran. A secure and enhanced
public key cryptosystem using double conjugacy search problem near-ring. Advances
in Mathematics: Scientific Journal, 9(3):1389–1395, Jul 2020.

[12] Illia Itenberg, Grigory Mikhalkin, and Eugenii Shustin. Tropical Algebraic Geometry.
Birkhäuser Basel, 2009.

[13] Diane Maclagan and Bernd Sturmfels. Introduction to tropical geometry. Graduate
Studies in Mathematics, Apr 2015.

[14] Sara Kalǐsnik and Davorin Lešnik. Symmetric polynomials in tropical algebra semir-
ings. Journal of Symbolic Computation, 93:100–119, Jul 2019.

[15] Dima Grigoriev and Vladimir Shpilrain. Tropical cryptography. Communications in
Algebra, 42(6):2624–2632, Jun 2014.

[16] Huawei Huang and Chunhua Li. Tropical cryptography based on multiple exponen-
tiation problem of matrices. Security and Communication Networks, 2022:1–9, Sep
2022.

[17] Mariana Ivanova Durcheva. Tres: Tropical encryption scheme based on double key
exchange. European Journal of Information Technologies and Computer Science,
2(4):11–17, Aug 2022.

[18] Sulaiman Alhussaini, Craig Collett, and Sergĕı Sergeev. On the tropical two-sided
discrete logarithm and a key exchange protocol based on the tropical algebra of pairs.
Communications in Algebra, 52(10):4115–4134, 2024.

[19] Matvei Kotov and Alexander Ushakov. Analysis of a key exchange protocol based
on tropical matrix algebra. Journal of Mathematical Cryptology, 12(3):137–141, Sep
2018.

[20] Dylan Rudy and Chris Monico. Remarks on a tropical key exchange system. Journal
of Mathematical Cryptology, 15(1):280–283, Dec 2020.