# Tropical Cryptography Based on Multiple Exponentiation Problem of Matrices

Authors: Huawei Huang; Chunhua Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Because there is no multiplication of numbers in tropical algebra and the problem of solving the systems of polynomial equations in tropical algebra is NP-hard, in recent years some public key cryptography based on tropical semiring has been proposed. But most of them have some defects. This paper proposes new public key cryptosystems based on tropical matrices. The security of the cryptosystem relies on the difficulty of the problem of finding multiple exponentiations of tropical matrices given the product of the matrices powers when the subsemiring is hidden. This problem is a generalization of the discrete logarithm problem. But the problem generally cannot be reduced to discrete logarithm problem or hidden subgroup problem in polynomial time. Since the generating matrix of the used commutative subsemirings is hidden and the public key matrices are the product of more than two unknown matrices, the cryptosystems can resist KU attack and other known attacks. The cryptosystems based on multiple exponentiation problem can be considered as a potential postquantum cryptosystem.


---

## Body

## 1. Introduction

Contemporary public key cryptography relies mainly on two computational problems, integer factorization problem, and discrete logarithm problem. For example, Diffie–Hellman key exchange protocol and ElGamal encryption scheme are based on discrete logarithm problem [1, 2]. Shor proposed a quantum algorithm which can solve integer factorization problem and discrete logarithm problem in polynomial time on a quantum computer [3]. So, it is a research focus of cryptography to develop other new cryptosystems. The traditional cryptosystems are based on various commutative rings, such as finite field, residue class ring, and integer ring [4–8]. Many cryptologists hope to find other algebraic structures to build new public key cryptosystems.In 2007, Maze, Monico, and Rosenthal proposed one of the first cryptosystems based on semigroups and semirings [9], using some ideas from [10], as well as from their previous article [11]. However, then it was broken by Steinwandt et al. [12]. Atani published a cryptosystem using semimodules over factor semirings [13]. Durcheva applied some idempotent semirings to construct cryptographic protocols [14]. A survey on semigroup action problem and its cryptographic applications was given by Goel, Gupta, and Dass [15].Grigoriev and Shpilrain proved that the problem of solving the systems of min-plus polynomial equations in tropical algebra is NP-hard and suggested using a min-plus (tropical) semiring to design public key cryptosystem [16]. An obvious advantage of using tropical algebras as platforms is unparalleled efficiency because in tropical schemes, one does not have to perform any multiplications of numbers since tropical multiplication is the usual addition. But “tropical powers” of an element exhibit some patterns, even if such an element is a matrix over a tropical algebra. This weakness was exploited by Kotov and Ushakov to arrange a fairly successful attack on one of Grigoriev and Shpilrain’s schemes [17]. In 2019, Grigoreiv and Shpilrain improved the original scheme and proposed the public key cryptosystems based on semi-direct product of tropical matrix semiring [18]. However, some attacks on the improved protocols are recently suggested by Rudy and Monico [19], Isaac and Kahrobei [20], and Muanalifah and Sergeev [21]. In order to remedy Grigoreiv–Shpilrain’s protocols, Muanalifah and Sergeev suggested some modifications that use two classes of commuting matrices in tropical algebra [22]. But the authors also pointed out that their modifications cannot resist the generalized KU attack since the user’s secret matrix can still be expressed in the linear form of the power of the basic elementary matrix.Our contribution: This paper provides a new public key cryptosystem based on tropical matrices. The security of the cryptosystem relies on the difficulty of the problem of finding multiple exponentiation of tropical matrices, which is a class of semigroup action problem proposed by Maze in [11]. The multiple exponentiation problem is also a generalization of the discrete logarithm problem. However, the problem generally cannot be reduced to discrete logarithm problem or hidden subgroup problem in polynomial time. Since the generating matrix of the used commutative subsemirings is hidden and the public key matrices are the product of more than two unknown matrices, the cryptosystems can resist KU attack and other known attacks. It is seemed that our cryptosystems based on multiple exponentiation problem can be considered as a potential postquantum cryptosystem.The remainder of this paper is organized as follows. In Section2, some preliminaries on tropical semiring are given. In Section 3, we define the multiple exponentiation problem of tropical matrices. In section 4, a key exchange protocol and a public key encryption scheme based on multiple exponentiation problem are presented. Finally, in Section 5 the possible attacks, parameter selection, and efficiency of the cryptosystems are discussed.


## 2. Preliminaries

Notation. In this paper, matrices are generally denoted by the capital letters. In order to facilitate future references, frequently used notations are listed below with their meanings.ℤ+ is set of all non-negative integers; ℤ+x is polynomial semiring over ℤ+; Mnℤ+ is set of all n×n matrices over ℤ+; ℤ+C is set of all polynomials of matrix C∈Mnℤ+; Z is tropical semiring of integers ℤ∪∞; Zx is tropical polynomial semiring over Z; MkZ is set of all k×k tropical matrices over Z; ZN is set of all tropical polynomials of tropical matrix N∈MkZ; H⟶ is the vector H1,H2,…,Hn, where Hi∈ZN.


### 2.1. Tropical Semiring over Integer

A semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.Definition 1.
(see [23]) A nonempty set ℛ with two binary operations + and ⋅ is called a semiring if(1)
ℛ,+ is a commutative monoid with identity element 0;(2)
ℛ,⋅ is a monoid with identity element 1≠0;(3)
Both distributive laws hold inℛ;(4)
a⋅0=0⋅a=0 for all a∈ℛ.
If a semiring’s multiplication is commutative, then it is called acommutative semiring.Definition 2.
(see [16]) The tropical commutative semiring of integer is the set Z=ℤ∪∞ with two operations as follows:(1)x⊕y=minx,y,x⊗y=x+y.
The special “∞” satisfies the equations:(2)∞⊕x=x,∞⊗x=∞.
It is straightforward to see thatZ,⊕,⊗ is a commutative semiring. In fact, ∞ is the identity element of Z,⊕ and 0 is the identity element of Z,⊕.
Just as in the classical case, we define the set of all tropical polynomials overZ in the indeterminate x. Let(3)Zx=an⊗xn⊕an−1⊗xn−1⊕,…,⊕a1⊗x⊕a0|ai∈Zandn≥0.
The tropical polynomial⊕ operation and ⊗ operation in Zxare similar to the classical polynomial addition and multiplication; however, every “+” calculation has to be substituted by a ⊕ operation of Z, and every “⋅” calculation by a ⊗ operation of Z. It is easy to verify that Zx is a commutative semiring with respect to the tropical polynomial ⊕ and ⊗ operations.


### 2.2. Tropical Matrix Semiring over Integer

MkZ denotes the set of all k×k matrices over Z. We can also define the tropical matrix ⊕ and ⊗ operations. To perform the A⊕B operation, the elements mij of the resulting matrix M are set to be equal to aij⊕bij. The tropical matrix ⊗ operation is similar to the usual matrix multiplication; however, every “+” calculation has to be substituted by a ⊕ operation of Z, and every “⋅” calculation by a ⊗ operation of Z. MkZ is a noncommutative semiring with respect to the tropical matrix ⊕ and ⊗ operations.Example 1.
(4)4−5270⊕10319=4−510,4−5270⊗10319=−4419,10319⊗4−5270=1435−4.
The role of the identity matrixI is played by the matrix that has “0” s on the diagonal and ∞ elsewhere. Similarly, a scalar matrix would be a matrix with an element λ∈S on the diagonal and ∞ elsewhere. Such a matrix commutes with any other square matrix (of the same size). Multiplying a matrix by a scalar amounts to multiplying it by the corresponding scalar matrix.Example 2.
(5)3⊗4−5270=3∞∞3⊗4−5270=7−2303.
Then, tropical diagonal matrices have something on the diagonal and∞ elsewhere. Note that, in contrast to the “classical” situation, it is rather rare that a “tropical” matrix is invertible. More specifically, the only invertible tropical matrices are those that are obtained from a diagonal matrix by permuting rows and/or columns.
For a matrixN∈MkZ, denote(6)ZN=an⊗Nn⊕an−1⊗Nn−1⊕,…,⊕a1⊗N⊕a0⊗I|ai∈Zandn≥0,where Nm means N⊗,…,⊗N (m times). It is clear that ZN is a commutative subsemiring of MkZ with respect to the tropical matrix addition and multiplication.


## 2.1. Tropical Semiring over Integer

A semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.Definition 1.
(see [23]) A nonempty set ℛ with two binary operations + and ⋅ is called a semiring if(1)
ℛ,+ is a commutative monoid with identity element 0;(2)
ℛ,⋅ is a monoid with identity element 1≠0;(3)
Both distributive laws hold inℛ;(4)
a⋅0=0⋅a=0 for all a∈ℛ.
If a semiring’s multiplication is commutative, then it is called acommutative semiring.Definition 2.
(see [16]) The tropical commutative semiring of integer is the set Z=ℤ∪∞ with two operations as follows:(1)x⊕y=minx,y,x⊗y=x+y.
The special “∞” satisfies the equations:(2)∞⊕x=x,∞⊗x=∞.
It is straightforward to see thatZ,⊕,⊗ is a commutative semiring. In fact, ∞ is the identity element of Z,⊕ and 0 is the identity element of Z,⊕.
Just as in the classical case, we define the set of all tropical polynomials overZ in the indeterminate x. Let(3)Zx=an⊗xn⊕an−1⊗xn−1⊕,…,⊕a1⊗x⊕a0|ai∈Zandn≥0.
The tropical polynomial⊕ operation and ⊗ operation in Zxare similar to the classical polynomial addition and multiplication; however, every “+” calculation has to be substituted by a ⊕ operation of Z, and every “⋅” calculation by a ⊗ operation of Z. It is easy to verify that Zx is a commutative semiring with respect to the tropical polynomial ⊕ and ⊗ operations.


## 2.2. Tropical Matrix Semiring over Integer

MkZ denotes the set of all k×k matrices over Z. We can also define the tropical matrix ⊕ and ⊗ operations. To perform the A⊕B operation, the elements mij of the resulting matrix M are set to be equal to aij⊕bij. The tropical matrix ⊗ operation is similar to the usual matrix multiplication; however, every “+” calculation has to be substituted by a ⊕ operation of Z, and every “⋅” calculation by a ⊗ operation of Z. MkZ is a noncommutative semiring with respect to the tropical matrix ⊕ and ⊗ operations.Example 1.
(4)4−5270⊕10319=4−510,4−5270⊗10319=−4419,10319⊗4−5270=1435−4.
The role of the identity matrixI is played by the matrix that has “0” s on the diagonal and ∞ elsewhere. Similarly, a scalar matrix would be a matrix with an element λ∈S on the diagonal and ∞ elsewhere. Such a matrix commutes with any other square matrix (of the same size). Multiplying a matrix by a scalar amounts to multiplying it by the corresponding scalar matrix.Example 2.
(5)3⊗4−5270=3∞∞3⊗4−5270=7−2303.
Then, tropical diagonal matrices have something on the diagonal and∞ elsewhere. Note that, in contrast to the “classical” situation, it is rather rare that a “tropical” matrix is invertible. More specifically, the only invertible tropical matrices are those that are obtained from a diagonal matrix by permuting rows and/or columns.
For a matrixN∈MkZ, denote(6)ZN=an⊗Nn⊕an−1⊗Nn−1⊕,…,⊕a1⊗N⊕a0⊗I|ai∈Zandn≥0,where Nm means N⊗,…,⊗N (m times). It is clear that ZN is a commutative subsemiring of MkZ with respect to the tropical matrix addition and multiplication.


## 3. Multiple Exponentiation Problem of Tropical Matrices

### 3.1. Companion Matrix of Polynomial over Integer Ringℤ

Letf0,f1,…,fn−1 be non-negative integers and f0>0. The companion matrix of a monic polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn is given by the n×n matrix(7)C=00…0f010…0f101…0f2⋮⋮⋱⋮⋮00…1fn−1.Note that the entries ofC are all non-negative. Denote(8)ℤ+C=pC|px∈ℤ+x.It is easy to verify thatℤ+C is a commutative subsemiring of Mnℤ.


### 3.2. Matrix Semigroupℤ+C Action on ZNn

Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let A=aijn×n∈ℤ+C, N∈MkZ, and H⟶=H1,H2,…,Hn∈ZNn. Consider an action ∗ of the multiplicative semigroup ℤ+C on the Cartesian product ZNn as below:(9)A∗H⟶=A∗H1,H2,…,Hn=∏i=1nHia1i,∏i=1nHia2i,…,∏i=1nHiani,where Hiaji means Hi⊗⋯⊗Hi (aji times). By the commutativity of ZN, it is easy to prove that “∗” is a semigroup action of ℤ+C on ZNn. In fact, a similar semigroup action was first defined by Maze in [11], where the action of ℤC on the group direct product Gn was considered.Example 3.
Letfx=x2−2. The companion matrix of fx is C=0210. Let N∈M3Z as follows.(10)N=6230238775518647.
LetH⟶=H1,H2∈ZN2 as follows.(11)H1=384336672068144238,H2=253838571563163225.
LetA=3E+5C=31053. Then,(12)A∗H⟶=A∗H1,H2=H13⊗H210,H15⊗H23=275233281252210258269227275,202168211187145193189162202.


### 3.3. Multiple Exponentiation Problem of Tropical Matrices

Definition 3.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶=H1,H2,…,Hn∈ZNn. Suppose that U⟶=A∗H⟶, where A∈ℤ+C. The multiple exponentiation problem of tropical matrices is to find A∈ℤ+C, given fx, H⟶, and U⟶. (Note that N is unknown.) For simplicity, we abbreviate the problem to “ME problem.”Example 4.
Givenfx=x2−2, H⟶=H1,H2, and U⟶ as follows, we try to find A∈ℤ+C such that U⟶=A∗H⟶.(13)H⟶=384336672068144238,253838571563163225,U⟶=260218266237195243254212260,138123136142100148114117138.
FindingA∈ℤ+C such that U⟶=A∗H⟶ is equivalent to finding a0,a1∈ℤ+ such that U⟶=a0E+a1C∗H⟶. By a0E+a1C=a02a1a1a0, we have U⟶=H1a0H22a1,H1a1H2a0. That is,(14)384336672068144238a0⊗2538385715631632252a1=275233281252210258269227275384336672068144238a1⊗253838571563163225a0=202168211187145193189162202.
As we know, most results in ordinary algebra do not hold in tropical algebra. Therefore, the certain properties of ordinary matrices like determinant, eigenvalues, and Cayley–Hamilton theorem cannot be used. But ifH1∈H2 or H2∈H1, we can reduce the problem to discrete logarithm problem.Proposition 1.
SupposeH1∈H2 or H2∈H1, then the ME problem in Example 4 can be reduced to discrete logarithm problem in polynomial time.Proof.
LetU⟶=U1,U2. Then,(15)H1a0H22a1=U1H1a1H2a0=U2
SupposeH2∈〈〈H1〉. By solving a discrete logarithm problem in H1, we can get a positive integer m such that H2=H1m. So, the equations (15) are equivalent to the following equations.(16)H1a0+2ma1=U1H1a1+ma0=U2.
In this case,U1,U2∈H1. By solving two discrete logarithm problems in H1, we can get two positive integers t1,t2 such that U1=H1t1 and U2=H1t2. Therefore,(17)a0+2ma1=t1a1+ma0=t2
It is clear that we can obtaina0,a1 by solving a system of linear equations.Proposition 2.
If there exists a componentHi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1, then the ME problem can be reduced to discrete logarithm problem in polynomial time.IfH1∉H2 and H2∉H1, the problem of finding a0,a1 from equation (14) cannot be reduced to discrete logarithm problem. In fact, in Example 4, the conditions are indeed satisfied.In order to resist some other potential method of solving ME problem, we stress the condition thatN is unknown. Since the matrix N is unknown, we cannot express H1 and H2 as the polynomials of N. (Even if N is known, we have not found any effective method to find a0 and a1.).Remark 1.
Assume thata0,a1∈0,s−1. Hence, in the example the total number of steps to solve ME problem by brute-force attack is s2.
Generally, assume thatA=∑i=0naiCiai∈0,s−1. Then, the total number of steps to solve ME problem by force attack is sn.


## 3.1. Companion Matrix of Polynomial over Integer Ringℤ

Letf0,f1,…,fn−1 be non-negative integers and f0>0. The companion matrix of a monic polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn is given by the n×n matrix(7)C=00…0f010…0f101…0f2⋮⋮⋱⋮⋮00…1fn−1.Note that the entries ofC are all non-negative. Denote(8)ℤ+C=pC|px∈ℤ+x.It is easy to verify thatℤ+C is a commutative subsemiring of Mnℤ.


## 3.2. Matrix Semigroupℤ+C Action on ZNn

Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let A=aijn×n∈ℤ+C, N∈MkZ, and H⟶=H1,H2,…,Hn∈ZNn. Consider an action ∗ of the multiplicative semigroup ℤ+C on the Cartesian product ZNn as below:(9)A∗H⟶=A∗H1,H2,…,Hn=∏i=1nHia1i,∏i=1nHia2i,…,∏i=1nHiani,where Hiaji means Hi⊗⋯⊗Hi (aji times). By the commutativity of ZN, it is easy to prove that “∗” is a semigroup action of ℤ+C on ZNn. In fact, a similar semigroup action was first defined by Maze in [11], where the action of ℤC on the group direct product Gn was considered.Example 3.
Letfx=x2−2. The companion matrix of fx is C=0210. Let N∈M3Z as follows.(10)N=6230238775518647.
LetH⟶=H1,H2∈ZN2 as follows.(11)H1=384336672068144238,H2=253838571563163225.
LetA=3E+5C=31053. Then,(12)A∗H⟶=A∗H1,H2=H13⊗H210,H15⊗H23=275233281252210258269227275,202168211187145193189162202.


## 3.3. Multiple Exponentiation Problem of Tropical Matrices

Definition 3.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶=H1,H2,…,Hn∈ZNn. Suppose that U⟶=A∗H⟶, where A∈ℤ+C. The multiple exponentiation problem of tropical matrices is to find A∈ℤ+C, given fx, H⟶, and U⟶. (Note that N is unknown.) For simplicity, we abbreviate the problem to “ME problem.”Example 4.
Givenfx=x2−2, H⟶=H1,H2, and U⟶ as follows, we try to find A∈ℤ+C such that U⟶=A∗H⟶.(13)H⟶=384336672068144238,253838571563163225,U⟶=260218266237195243254212260,138123136142100148114117138.
FindingA∈ℤ+C such that U⟶=A∗H⟶ is equivalent to finding a0,a1∈ℤ+ such that U⟶=a0E+a1C∗H⟶. By a0E+a1C=a02a1a1a0, we have U⟶=H1a0H22a1,H1a1H2a0. That is,(14)384336672068144238a0⊗2538385715631632252a1=275233281252210258269227275384336672068144238a1⊗253838571563163225a0=202168211187145193189162202.
As we know, most results in ordinary algebra do not hold in tropical algebra. Therefore, the certain properties of ordinary matrices like determinant, eigenvalues, and Cayley–Hamilton theorem cannot be used. But ifH1∈H2 or H2∈H1, we can reduce the problem to discrete logarithm problem.Proposition 1.
SupposeH1∈H2 or H2∈H1, then the ME problem in Example 4 can be reduced to discrete logarithm problem in polynomial time.Proof.
LetU⟶=U1,U2. Then,(15)H1a0H22a1=U1H1a1H2a0=U2
SupposeH2∈〈〈H1〉. By solving a discrete logarithm problem in H1, we can get a positive integer m such that H2=H1m. So, the equations (15) are equivalent to the following equations.(16)H1a0+2ma1=U1H1a1+ma0=U2.
In this case,U1,U2∈H1. By solving two discrete logarithm problems in H1, we can get two positive integers t1,t2 such that U1=H1t1 and U2=H1t2. Therefore,(17)a0+2ma1=t1a1+ma0=t2
It is clear that we can obtaina0,a1 by solving a system of linear equations.Proposition 2.
If there exists a componentHi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1, then the ME problem can be reduced to discrete logarithm problem in polynomial time.IfH1∉H2 and H2∉H1, the problem of finding a0,a1 from equation (14) cannot be reduced to discrete logarithm problem. In fact, in Example 4, the conditions are indeed satisfied.In order to resist some other potential method of solving ME problem, we stress the condition thatN is unknown. Since the matrix N is unknown, we cannot express H1 and H2 as the polynomials of N. (Even if N is known, we have not found any effective method to find a0 and a1.).Remark 1.
Assume thata0,a1∈0,s−1. Hence, in the example the total number of steps to solve ME problem by brute-force attack is s2.
Generally, assume thatA=∑i=0naiCiai∈0,s−1. Then, the total number of steps to solve ME problem by force attack is sn.


## 4. Public Key Cryptosystems Based on Tropical Matrix

In this section, we give a key exchange protocol similar to Diffie–Hellman protocol and a public key encryption scheme similar to ElGamal encryption scheme.


### 4.1. Key Exchange Protocol Based on Tropical Matrix

Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn and H⟶∈ZNn such that there exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. The public parameters of the protocol are fx, H⟶. Key change protocol based on tropical matrix is the following.


#### 4.1.1. Protocol 4.1.1

(1)
Alice selects at randomn private integers a0,a1,…,an−1 in 0,s−1 and computesA=an−1Cn−1+⋯+a1C+a0E=aijn×n. Bob selects at random n private integers b0,b1,…,bn−1 in 0,s−1 and computes(18)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Alice computesU⟶=A∗H⟶ and sends to Bob the matrix U⟶. And Bob computes V⟶=B∗H⟶ and sends to Alice the matrix V⟶.(3)
Alice computes(19)KAlice=A∗V⟶=A∗B∗H⟶=A⋅B∗H⟶.and Bob computes(20)KBob=B∗U⟶=B∗A∗H⟶=B⋅A∗H⟶,where “⋅” is the matrix multiplication in ℤ+C.Sinceℤ+C is commutative, we have A⋅B=B⋅A and KAlice=KBob. So, Alice and Bob share a common secret key.Definition 4.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. Suppose that U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. The computational ME problem is to find the matrix vector K⟶ such that K⟶=AB∗H⟶, given fx, H⟶, U⟶, and V⟶. For simplicity, we abbreviate the problem to “CME problem.”Proposition 3.
An algorithm that solves ME problem can be used to solve CME problem.Proposition 4.
Finding the common secret key from the public information of Protocol 4.1.1 is equivalent to solving the CME problem.


### 4.2. Public Key Encryption Scheme Based on Tropical Matrix

#### 4.2.1. Scheme 4.2.1

Key generation.Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. The public parameters are fx, H⟶. The key generation center chooses at random integers a0,a1,…,an−1∈0,s−1 and computes(21)A=an−1Cn−1+⋯+a1C+a0E=aijn×n,U⟶=A∗H⟶.The public key of Alice isU⟶. The private key of Alice is A (or a0,a1,…,an−1).Encryption.Bob wants to send a plaintext messagesM⟶∈Mkℤn to Alice.(1)
Bob chooses at random integersb0,b1,…,bn−1 in 0,s−1 and computes(22)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Bob computesV⟶=B∗H⟶ as a part of ciphertext.(3)
Bob computesQ⟶=M⟶+B∗U⟶ as the rest of the ciphertext, where “+” is the ordinary integer matrix vector addition.(4)
Bob sends the ciphertextV⟶,Q⟶ to Alice.Decryption.Alice receives the ciphertextV⟶,Q⟶ and tries to decrypt it.(1)
Using her private keyA, Alice computes W⟶=A∗V⟶.(2)
Alice computesQ⟶−W⟶, where “-” is the ordinary integer matrix vector subtraction.Since(23)Q⟶−W⟶=M⟶+B∗U⟶−A∗V⟶=M⟶+B∗A∗H⟶−A∗B∗H⟶=M⟶+BA∗H⟶−AB∗H⟶=M⟶,Alice gets the plaintext messagesM⟶.Definition 5.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. Suppose U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. Let R∈ZNn. The decisional ME problem is to decide whether R⟶=AB∗H⟶, given fx, H⟶, U⟶, V⟶, and R⟶. For simplicity, we abbreviate it to “DME problem.”Proposition 5.
An algorithm that solves CME problem can be used to solve DME problem.Theorem 1.
An algorithm that solves DME problem can be used to decide the validity of the ciphertexts of Scheme 4.2.1, and an algorithm that decides the validity of the ciphertexts of Scheme 4.2.1 can be used to solve DME problem.Proof.
Suppose first that the algorithmA1 can decide whether a decryption of Scheme 4.2.1 is correct. In other words, when given the inputs fx, H⟶, U⟶, V⟶,Q⟶, M⟶, the algorithm A1 outputs “yes” if M⟶ is the decryption of V⟶,Q⟶ and outputs “no” otherwise. Let us use A1 to solve the DME problem. Suppose you are given p, fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, and you want to decide whether or not R⟶=AB∗H⟶. Let Q⟶=R⟶ and M⟶=0k,0k,…,0k, where 0k is the k×k zero matrix of Mkℤ. Input all of these into A1. Note that in the present setup, A is the secret key. The correct decryption of V⟶,Q⟶ is(24)Q⟶−A∗V⟶=R⟶−A∗B∗H⟶=R⟶−AB∗H⟶.
Therefore,A1 outputs “yes” exactly when M⟶=0k,0k,…,0k is the same as R⟶−AB∗H⟶, namely, when R⟶=AB∗H⟶. This solves the decision DME problem.
Conversely, suppose an algorithmA2 can solve the DME problem. This means that if you give A2 inputs fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, then A2 outputs “yes” if R⟶=AB∗H⟶ and outputs “no” if not. Let M⟶ be the claimed decryption of the ciphertext V⟶,Q⟶. Input Q⟶−M⟶ as R⟶. Note that M⟶ is the correct plaintext for the ciphertext V⟶,Q⟶ if and only if M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, which happens if and only if Q⟶−M⟶=AB∗H⟶. Therefore, M⟶ is the correct plaintext if and only if R⟶=AB∗H⟶. Therefore, with these inputs, A2 outputs “yes” exactly when M⟶ is the correct plaintext.Theorem 2.
An algorithm that solves CME problem can be used to decrypt the ciphertexts of Scheme 4.2.1, and an algorithm that decrypts the ciphertexts of Scheme 4.2.1 can be used to solve CME problem.Proof.
If we have an algorithmA3 that can decrypt all ciphertexts of Scheme 4.2.1, then input U⟶=A∗H⟶ and V⟶=B∗H⟶. Take any vector for Q⟶. Then, A3 outputs(25)M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶.
Therefore,Q⟶−M⟶ yields the solution AB∗H⟶ to the CME problem.
Conversely, suppose we have an algorithmA4 that can solve CME problem. If we have an ciphertext V⟶,Q⟶, then we input U⟶=A∗H⟶ and V⟶=B∗H⟶. Then, A4 outputs AB∗H⟶. Since M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, we obtain the plaintext M⟶ □.


## 4.1. Key Exchange Protocol Based on Tropical Matrix

Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn and H⟶∈ZNn such that there exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. The public parameters of the protocol are fx, H⟶. Key change protocol based on tropical matrix is the following.


### 4.1.1. Protocol 4.1.1

(1)
Alice selects at randomn private integers a0,a1,…,an−1 in 0,s−1 and computesA=an−1Cn−1+⋯+a1C+a0E=aijn×n. Bob selects at random n private integers b0,b1,…,bn−1 in 0,s−1 and computes(18)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Alice computesU⟶=A∗H⟶ and sends to Bob the matrix U⟶. And Bob computes V⟶=B∗H⟶ and sends to Alice the matrix V⟶.(3)
Alice computes(19)KAlice=A∗V⟶=A∗B∗H⟶=A⋅B∗H⟶.and Bob computes(20)KBob=B∗U⟶=B∗A∗H⟶=B⋅A∗H⟶,where “⋅” is the matrix multiplication in ℤ+C.Sinceℤ+C is commutative, we have A⋅B=B⋅A and KAlice=KBob. So, Alice and Bob share a common secret key.Definition 4.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. Suppose that U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. The computational ME problem is to find the matrix vector K⟶ such that K⟶=AB∗H⟶, given fx, H⟶, U⟶, and V⟶. For simplicity, we abbreviate the problem to “CME problem.”Proposition 3.
An algorithm that solves ME problem can be used to solve CME problem.Proposition 4.
Finding the common secret key from the public information of Protocol 4.1.1 is equivalent to solving the CME problem.


## 4.1.1. Protocol 4.1.1

(1)
Alice selects at randomn private integers a0,a1,…,an−1 in 0,s−1 and computesA=an−1Cn−1+⋯+a1C+a0E=aijn×n. Bob selects at random n private integers b0,b1,…,bn−1 in 0,s−1 and computes(18)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Alice computesU⟶=A∗H⟶ and sends to Bob the matrix U⟶. And Bob computes V⟶=B∗H⟶ and sends to Alice the matrix V⟶.(3)
Alice computes(19)KAlice=A∗V⟶=A∗B∗H⟶=A⋅B∗H⟶.and Bob computes(20)KBob=B∗U⟶=B∗A∗H⟶=B⋅A∗H⟶,where “⋅” is the matrix multiplication in ℤ+C.Sinceℤ+C is commutative, we have A⋅B=B⋅A and KAlice=KBob. So, Alice and Bob share a common secret key.Definition 4.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. Suppose that U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. The computational ME problem is to find the matrix vector K⟶ such that K⟶=AB∗H⟶, given fx, H⟶, U⟶, and V⟶. For simplicity, we abbreviate the problem to “CME problem.”Proposition 3.
An algorithm that solves ME problem can be used to solve CME problem.Proposition 4.
Finding the common secret key from the public information of Protocol 4.1.1 is equivalent to solving the CME problem.


## 4.2. Public Key Encryption Scheme Based on Tropical Matrix

### 4.2.1. Scheme 4.2.1

Key generation.Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. The public parameters are fx, H⟶. The key generation center chooses at random integers a0,a1,…,an−1∈0,s−1 and computes(21)A=an−1Cn−1+⋯+a1C+a0E=aijn×n,U⟶=A∗H⟶.The public key of Alice isU⟶. The private key of Alice is A (or a0,a1,…,an−1).Encryption.Bob wants to send a plaintext messagesM⟶∈Mkℤn to Alice.(1)
Bob chooses at random integersb0,b1,…,bn−1 in 0,s−1 and computes(22)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Bob computesV⟶=B∗H⟶ as a part of ciphertext.(3)
Bob computesQ⟶=M⟶+B∗U⟶ as the rest of the ciphertext, where “+” is the ordinary integer matrix vector addition.(4)
Bob sends the ciphertextV⟶,Q⟶ to Alice.Decryption.Alice receives the ciphertextV⟶,Q⟶ and tries to decrypt it.(1)
Using her private keyA, Alice computes W⟶=A∗V⟶.(2)
Alice computesQ⟶−W⟶, where “-” is the ordinary integer matrix vector subtraction.Since(23)Q⟶−W⟶=M⟶+B∗U⟶−A∗V⟶=M⟶+B∗A∗H⟶−A∗B∗H⟶=M⟶+BA∗H⟶−AB∗H⟶=M⟶,Alice gets the plaintext messagesM⟶.Definition 5.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. Suppose U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. Let R∈ZNn. The decisional ME problem is to decide whether R⟶=AB∗H⟶, given fx, H⟶, U⟶, V⟶, and R⟶. For simplicity, we abbreviate it to “DME problem.”Proposition 5.
An algorithm that solves CME problem can be used to solve DME problem.Theorem 1.
An algorithm that solves DME problem can be used to decide the validity of the ciphertexts of Scheme 4.2.1, and an algorithm that decides the validity of the ciphertexts of Scheme 4.2.1 can be used to solve DME problem.Proof.
Suppose first that the algorithmA1 can decide whether a decryption of Scheme 4.2.1 is correct. In other words, when given the inputs fx, H⟶, U⟶, V⟶,Q⟶, M⟶, the algorithm A1 outputs “yes” if M⟶ is the decryption of V⟶,Q⟶ and outputs “no” otherwise. Let us use A1 to solve the DME problem. Suppose you are given p, fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, and you want to decide whether or not R⟶=AB∗H⟶. Let Q⟶=R⟶ and M⟶=0k,0k,…,0k, where 0k is the k×k zero matrix of Mkℤ. Input all of these into A1. Note that in the present setup, A is the secret key. The correct decryption of V⟶,Q⟶ is(24)Q⟶−A∗V⟶=R⟶−A∗B∗H⟶=R⟶−AB∗H⟶.
Therefore,A1 outputs “yes” exactly when M⟶=0k,0k,…,0k is the same as R⟶−AB∗H⟶, namely, when R⟶=AB∗H⟶. This solves the decision DME problem.
Conversely, suppose an algorithmA2 can solve the DME problem. This means that if you give A2 inputs fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, then A2 outputs “yes” if R⟶=AB∗H⟶ and outputs “no” if not. Let M⟶ be the claimed decryption of the ciphertext V⟶,Q⟶. Input Q⟶−M⟶ as R⟶. Note that M⟶ is the correct plaintext for the ciphertext V⟶,Q⟶ if and only if M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, which happens if and only if Q⟶−M⟶=AB∗H⟶. Therefore, M⟶ is the correct plaintext if and only if R⟶=AB∗H⟶. Therefore, with these inputs, A2 outputs “yes” exactly when M⟶ is the correct plaintext.Theorem 2.
An algorithm that solves CME problem can be used to decrypt the ciphertexts of Scheme 4.2.1, and an algorithm that decrypts the ciphertexts of Scheme 4.2.1 can be used to solve CME problem.Proof.
If we have an algorithmA3 that can decrypt all ciphertexts of Scheme 4.2.1, then input U⟶=A∗H⟶ and V⟶=B∗H⟶. Take any vector for Q⟶. Then, A3 outputs(25)M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶.
Therefore,Q⟶−M⟶ yields the solution AB∗H⟶ to the CME problem.
Conversely, suppose we have an algorithmA4 that can solve CME problem. If we have an ciphertext V⟶,Q⟶, then we input U⟶=A∗H⟶ and V⟶=B∗H⟶. Then, A4 outputs AB∗H⟶. Since M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, we obtain the plaintext M⟶ □.


## 4.2.1. Scheme 4.2.1

Key generation.Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. There exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. The public parameters are fx, H⟶. The key generation center chooses at random integers a0,a1,…,an−1∈0,s−1 and computes(21)A=an−1Cn−1+⋯+a1C+a0E=aijn×n,U⟶=A∗H⟶.The public key of Alice isU⟶. The private key of Alice is A (or a0,a1,…,an−1).Encryption.Bob wants to send a plaintext messagesM⟶∈Mkℤn to Alice.(1)
Bob chooses at random integersb0,b1,…,bn−1 in 0,s−1 and computes(22)B=bn−1Cn−1+⋯+b1C+b0E=bijn×n.(2)
Bob computesV⟶=B∗H⟶ as a part of ciphertext.(3)
Bob computesQ⟶=M⟶+B∗U⟶ as the rest of the ciphertext, where “+” is the ordinary integer matrix vector addition.(4)
Bob sends the ciphertextV⟶,Q⟶ to Alice.Decryption.Alice receives the ciphertextV⟶,Q⟶ and tries to decrypt it.(1)
Using her private keyA, Alice computes W⟶=A∗V⟶.(2)
Alice computesQ⟶−W⟶, where “-” is the ordinary integer matrix vector subtraction.Since(23)Q⟶−W⟶=M⟶+B∗U⟶−A∗V⟶=M⟶+B∗A∗H⟶−A∗B∗H⟶=M⟶+BA∗H⟶−AB∗H⟶=M⟶,Alice gets the plaintext messagesM⟶.Definition 5.
Letf0,f1,…,fn−1 be non-negative integers and f0>0. Let C be the companion matrix of the polynomial fx=−f0−f1x−⋯−fn−1xn−1+xn. Let N∈MkZ and H⟶∈ZNn. Suppose U⟶=A∗H⟶ and V⟶=B∗H⟶, where A,B∈ℤ+C. Let R∈ZNn. The decisional ME problem is to decide whether R⟶=AB∗H⟶, given fx, H⟶, U⟶, V⟶, and R⟶. For simplicity, we abbreviate it to “DME problem.”Proposition 5.
An algorithm that solves CME problem can be used to solve DME problem.Theorem 1.
An algorithm that solves DME problem can be used to decide the validity of the ciphertexts of Scheme 4.2.1, and an algorithm that decides the validity of the ciphertexts of Scheme 4.2.1 can be used to solve DME problem.Proof.
Suppose first that the algorithmA1 can decide whether a decryption of Scheme 4.2.1 is correct. In other words, when given the inputs fx, H⟶, U⟶, V⟶,Q⟶, M⟶, the algorithm A1 outputs “yes” if M⟶ is the decryption of V⟶,Q⟶ and outputs “no” otherwise. Let us use A1 to solve the DME problem. Suppose you are given p, fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, and you want to decide whether or not R⟶=AB∗H⟶. Let Q⟶=R⟶ and M⟶=0k,0k,…,0k, where 0k is the k×k zero matrix of Mkℤ. Input all of these into A1. Note that in the present setup, A is the secret key. The correct decryption of V⟶,Q⟶ is(24)Q⟶−A∗V⟶=R⟶−A∗B∗H⟶=R⟶−AB∗H⟶.
Therefore,A1 outputs “yes” exactly when M⟶=0k,0k,…,0k is the same as R⟶−AB∗H⟶, namely, when R⟶=AB∗H⟶. This solves the decision DME problem.
Conversely, suppose an algorithmA2 can solve the DME problem. This means that if you give A2 inputs fx, H⟶, U⟶=A∗H⟶, V⟶=B∗H⟶, and R⟶, then A2 outputs “yes” if R⟶=AB∗H⟶ and outputs “no” if not. Let M⟶ be the claimed decryption of the ciphertext V⟶,Q⟶. Input Q⟶−M⟶ as R⟶. Note that M⟶ is the correct plaintext for the ciphertext V⟶,Q⟶ if and only if M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, which happens if and only if Q⟶−M⟶=AB∗H⟶. Therefore, M⟶ is the correct plaintext if and only if R⟶=AB∗H⟶. Therefore, with these inputs, A2 outputs “yes” exactly when M⟶ is the correct plaintext.Theorem 2.
An algorithm that solves CME problem can be used to decrypt the ciphertexts of Scheme 4.2.1, and an algorithm that decrypts the ciphertexts of Scheme 4.2.1 can be used to solve CME problem.Proof.
If we have an algorithmA3 that can decrypt all ciphertexts of Scheme 4.2.1, then input U⟶=A∗H⟶ and V⟶=B∗H⟶. Take any vector for Q⟶. Then, A3 outputs(25)M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶.
Therefore,Q⟶−M⟶ yields the solution AB∗H⟶ to the CME problem.
Conversely, suppose we have an algorithmA4 that can solve CME problem. If we have an ciphertext V⟶,Q⟶, then we input U⟶=A∗H⟶ and V⟶=B∗H⟶. Then, A4 outputs AB∗H⟶. Since M⟶=Q⟶−A∗V⟶=Q⟶−AB∗H⟶, we obtain the plaintext M⟶ □.


## 5. Possible Attacks, Parameter Selection, and Efficiency

### 5.1. Possible Attacks

(1)
Brute-force attack. Suppose thatA=an−1Cn−1+⋯+a1C+a0E=aijn×n and a0,a1,…,an−1∈0,s−1. It is clear that attacker has sn choices to choose A. So, the parameters s and n must satisfy sn≥280.(2)
Tropical matrix decomposition attack.Suppose thatU⟶=U1,U2,…,Un. If attacker can find A′=aij′n×n such that(26)H1a11′H2a12′…Hna1n′=U1H1a21′H2a22′…Hna2n′=U2………H1an1′H2an2′…Hnann′=Un,A′C=CA′.Then he can get the shared keyA⋅B∗H⟶ by A′ and the public information. He can perform the following steps to find A′.(i)
FactorUi=G1G2,…,Gn, where Gj∈Hji,j=1,2,…,n.(ii)
Findaij′ such that Hiaij′=Gii,j=1,2,…,n by solving discrete logarithm problem in Hi.(iii)
Verify whether or notA′C=CA′. If not, go to (i).However, it is hard to factorUi=G1G2⋯Gn, where Gj∈Hj and n>2. Generally, it is NP-hard by Shitov [24].(3)
KU attack. In our cryptosystems, the used commutative subsemiring in our cryptosystems is the subsemiringZN and N is unknown. This is different from that in literature [16]. They used two public tropical matrices M1,M2M1M2≠M2M1 and then adopted the commutative subsemiring ZM1,, ZM2. Let p1M1∈ZM1, p2M2∈ZM2, and p1M1p2M2=U. The security of the cryptosystem relies on the difficulty of the problem of finding S1∈ZM1 and S2∈ZM2 such that S1S2=U. Because the secrete matrix can be expressed as a polynomial of M. Kotov and Ushakov designed an efficient algorithm to attack the tropical key exchange protocol [17]. In our cryptosystems, since attacker does not know N, the KU attack will not work. To find N from public information, attacker is faced with the following problem.GivenH1,H2,…,Hn∈MkZ, find N∈MkZ such that(27)d19⊗N9⊕d18⊗N8⊕⋯⊕d11⊗N⊕d10⊗Ik=H1d29⊗N9⊕d28⊗N8⊕⋯⊕d21⊗N⊕d20⊗Ik=H2………dn9⊗N9⊕dn8⊗N8⊕⋯⊕dn1⊗N⊕dn0⊗Ik=Hn.wheredi9,di8,…,di1,di0i=1,2,…,n and N are all unknown. It is clear that this is a problem of solving systems of min-plus polynomial equations which is NP-hard [16].Even ifN is obtained by attacker. It seems also hard to find the private key matrix A from the public key U⟶=A∗H⟶. As we know, KU attack can only decompose a tropical matrix into the product of two matrices such as U=S1S2. If n>2, each component matrix of U⟶ is the product of matrices more than two. In this case, KU attack will also not work.(4)
Generalized KU attack. In order to remedy Grigoreiv–Shpilrain’s protocols, Muanalifah and Sergeev suggested some modifications that use two types of matrices that are Jones matrices and Linde–de la Puente matrices [22]. But the authors also pointed out that their modifications cannot resist the generalized KU attack which can also decompose the public matrix into the product of two Jones matrices (Linde–de la Puente matrices) expressed as the linear form of the tropical basic elementary matrix. In our cryptosystems, if n>2, then each component matrix of U⟶ is the product of matrices more than two. In this case, the generalized KU attack will also not work for our cryptosystems.(5)
RM attack. Grigoreiv and Shpilrain [18] improved the original scheme and proposed the public key cryptosystems based on semi-direct product of tropical matrix semiring. But the first component of semi-direct product multiplication contains the addition of tropical matrix. Because the addition operation of tropical matrix is idempotent, the powers of semi-direct product multiplication have partial order preservation. Using this property, Rudy and Monico designed a simple binary search algorithm and cracked the cryptosystem in [18]. In our cryptosystems, A∗H⟶ has not the addition operation of tropical matrix. So, our cryptosystems can resist this attack.(6)
Quantum attack. ME problem is the generalization of the discrete logarithm problem. As we know, the discrete logarithm problem can be reduced in polynomial time to hidden subgroup problem which can be solved in polynomial time by the generalized Shor quantum algorithm [25]. If the semigroup action is derived from a module over ring, there exist the similar reduction algorithms for the corresponding semigroup action problem. When the semigroup action is induced by a semimodule over semiring that cannot be embedded in a module, no effective reduction algorithm has been found for the corresponding semigroup action problem. It is easy to verify that “∗” is a semigroup action derived from the semimodule ZNn over the semiring ℤ+C and ME problem is indeed the corresponding semigroup action problem induced by the semimodule. Since the semimodule ZNn cannot be embedded in a module, ME problem cannot be reduced in polynomial time to hidden subgroup problem generally.Table1 provides the comparison among relevant tropical cryptographic schemes.Table 1
Comparison among relevant tropical schemes.
SchemesMathematical problemsKU attackRM attackG-KU attackGrigoriev [16]Two-side matrix action problem×√×Grigoriev [18]Semi-direct product problem√×√Muanalifah [22]Two-side matrix action problem√√×Our schemesMultiple exponentiation problem√√√Note. that √ means that the scheme can resist the corresponding attack, while × does not.


### 5.2. Parameter Selection and Efficiency

By Proposition2, if there exists a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1, then the ME problem can be reduced to discrete logarithm problem in polynomial time. To avoid this case, H⟶ needs to satisfy the condition that there exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. Note that N is unknown and H1,H2,…,Hn∈ZN. We can choose Hi such that(28)Hi=di9⊗N9⊕di8⊗N8⊕⋯⊕di1⊗N⊕di0⊗Ik,where di0,di1,…,di9 are integers selected randomly in 0,1024. Then, the number of possible Hi is 2100. Experiments show that it is easy to generate H1,H2,…,Hn satisfying the above condition.Generally, forN∈MkZ, the monogenic subsemigroup N is infinite. But for many tropical matrices N∈MkZ, there are non-negative integers l,m and integer e such that e⊗Nl=Nl+m. If l,m are the smallest non-negative integers such that e⊗Nl=Nl+m, then l is called the pseudo-index of the matrix N and m is called the pseudo-period of the matrix N. If the pseudo-indexes and the pseudo-periods of N and Hii=1,2,…,n are all small, then there may be some potential heuristic attacks. The pseudo-index of tropical matrix increases with the increase of k. Our experiments show that it is feasible to generate N and Hii=1,2,…,n with pseudo-indexes more than k2 (k<30). In A∗H⟶ and B∗H⟶, the entries of A, B are the exponents of Hi. Since A,B∈ℤC, the entries of C and s should not be too large. We recommend fx=xn−1 and(29)C=00…0110…0001…00⋮⋮⋱⋮⋮00…10.Then, the entries ofA, B are in 0,s−1 and the entries of AB are less than ns−12. To resist some potential heuristic attacks, we recommend the parameters s,n,k satisfying k2≥ns−12.If we use the “square-multiply” algorithm to compute the power of tropical matrix, then computingA∗H⟶ requires n2logs+nn−1 tropical matrix multiplications. The numbers of bit operations required for multiplying two tropical matrices of order k are Ok3. So, the total number of bit operations required for calculating A∗H⟶ is Ok3n2logs.The size of secret keya0,a1,…,an−1 is less than nlogs bits. Suppose the entries of the matrices N are in the range 0,T and Hi=∑j=09dij⊗N9 where dij∈0,d. Then, the size of public key U⟶ is less than n2k2logs−1d+9T bits.SelectT=100 and d=1024. Table 2 provides the upper bounds of the size of secrete key and public key for different values of k,n,s such that sn≈280 and k2≈ns−12. And in Table 2, we also compare the running time of the operation A∗H⟶ under different parameters (experimental platform: Intel(R) Core(TM) i7-4700MQ CPU @ 2.40 GHz).Table 2
Performance comparison under some different parameters.
knsUpper bound of sk (bit)Upper bound of pk (kB)Timing ofA∗H⟶ (s)9802806821.79814503807481.46319404808792.372233458010313.210283168011974.316


## 5.1. Possible Attacks

(1)
Brute-force attack. Suppose thatA=an−1Cn−1+⋯+a1C+a0E=aijn×n and a0,a1,…,an−1∈0,s−1. It is clear that attacker has sn choices to choose A. So, the parameters s and n must satisfy sn≥280.(2)
Tropical matrix decomposition attack.Suppose thatU⟶=U1,U2,…,Un. If attacker can find A′=aij′n×n such that(26)H1a11′H2a12′…Hna1n′=U1H1a21′H2a22′…Hna2n′=U2………H1an1′H2an2′…Hnann′=Un,A′C=CA′.Then he can get the shared keyA⋅B∗H⟶ by A′ and the public information. He can perform the following steps to find A′.(i)
FactorUi=G1G2,…,Gn, where Gj∈Hji,j=1,2,…,n.(ii)
Findaij′ such that Hiaij′=Gii,j=1,2,…,n by solving discrete logarithm problem in Hi.(iii)
Verify whether or notA′C=CA′. If not, go to (i).However, it is hard to factorUi=G1G2⋯Gn, where Gj∈Hj and n>2. Generally, it is NP-hard by Shitov [24].(3)
KU attack. In our cryptosystems, the used commutative subsemiring in our cryptosystems is the subsemiringZN and N is unknown. This is different from that in literature [16]. They used two public tropical matrices M1,M2M1M2≠M2M1 and then adopted the commutative subsemiring ZM1,, ZM2. Let p1M1∈ZM1, p2M2∈ZM2, and p1M1p2M2=U. The security of the cryptosystem relies on the difficulty of the problem of finding S1∈ZM1 and S2∈ZM2 such that S1S2=U. Because the secrete matrix can be expressed as a polynomial of M. Kotov and Ushakov designed an efficient algorithm to attack the tropical key exchange protocol [17]. In our cryptosystems, since attacker does not know N, the KU attack will not work. To find N from public information, attacker is faced with the following problem.GivenH1,H2,…,Hn∈MkZ, find N∈MkZ such that(27)d19⊗N9⊕d18⊗N8⊕⋯⊕d11⊗N⊕d10⊗Ik=H1d29⊗N9⊕d28⊗N8⊕⋯⊕d21⊗N⊕d20⊗Ik=H2………dn9⊗N9⊕dn8⊗N8⊕⋯⊕dn1⊗N⊕dn0⊗Ik=Hn.wheredi9,di8,…,di1,di0i=1,2,…,n and N are all unknown. It is clear that this is a problem of solving systems of min-plus polynomial equations which is NP-hard [16].Even ifN is obtained by attacker. It seems also hard to find the private key matrix A from the public key U⟶=A∗H⟶. As we know, KU attack can only decompose a tropical matrix into the product of two matrices such as U=S1S2. If n>2, each component matrix of U⟶ is the product of matrices more than two. In this case, KU attack will also not work.(4)
Generalized KU attack. In order to remedy Grigoreiv–Shpilrain’s protocols, Muanalifah and Sergeev suggested some modifications that use two types of matrices that are Jones matrices and Linde–de la Puente matrices [22]. But the authors also pointed out that their modifications cannot resist the generalized KU attack which can also decompose the public matrix into the product of two Jones matrices (Linde–de la Puente matrices) expressed as the linear form of the tropical basic elementary matrix. In our cryptosystems, if n>2, then each component matrix of U⟶ is the product of matrices more than two. In this case, the generalized KU attack will also not work for our cryptosystems.(5)
RM attack. Grigoreiv and Shpilrain [18] improved the original scheme and proposed the public key cryptosystems based on semi-direct product of tropical matrix semiring. But the first component of semi-direct product multiplication contains the addition of tropical matrix. Because the addition operation of tropical matrix is idempotent, the powers of semi-direct product multiplication have partial order preservation. Using this property, Rudy and Monico designed a simple binary search algorithm and cracked the cryptosystem in [18]. In our cryptosystems, A∗H⟶ has not the addition operation of tropical matrix. So, our cryptosystems can resist this attack.(6)
Quantum attack. ME problem is the generalization of the discrete logarithm problem. As we know, the discrete logarithm problem can be reduced in polynomial time to hidden subgroup problem which can be solved in polynomial time by the generalized Shor quantum algorithm [25]. If the semigroup action is derived from a module over ring, there exist the similar reduction algorithms for the corresponding semigroup action problem. When the semigroup action is induced by a semimodule over semiring that cannot be embedded in a module, no effective reduction algorithm has been found for the corresponding semigroup action problem. It is easy to verify that “∗” is a semigroup action derived from the semimodule ZNn over the semiring ℤ+C and ME problem is indeed the corresponding semigroup action problem induced by the semimodule. Since the semimodule ZNn cannot be embedded in a module, ME problem cannot be reduced in polynomial time to hidden subgroup problem generally.Table1 provides the comparison among relevant tropical cryptographic schemes.Table 1
Comparison among relevant tropical schemes.
SchemesMathematical problemsKU attackRM attackG-KU attackGrigoriev [16]Two-side matrix action problem×√×Grigoriev [18]Semi-direct product problem√×√Muanalifah [22]Two-side matrix action problem√√×Our schemesMultiple exponentiation problem√√√Note. that √ means that the scheme can resist the corresponding attack, while × does not.


## 5.2. Parameter Selection and Efficiency

By Proposition2, if there exists a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1, then the ME problem can be reduced to discrete logarithm problem in polynomial time. To avoid this case, H⟶ needs to satisfy the condition that there exists not a component Hi of H⟶ such that ∀j≠iHj∈Hii,j=0,1,…,n−1. Note that N is unknown and H1,H2,…,Hn∈ZN. We can choose Hi such that(28)Hi=di9⊗N9⊕di8⊗N8⊕⋯⊕di1⊗N⊕di0⊗Ik,where di0,di1,…,di9 are integers selected randomly in 0,1024. Then, the number of possible Hi is 2100. Experiments show that it is easy to generate H1,H2,…,Hn satisfying the above condition.Generally, forN∈MkZ, the monogenic subsemigroup N is infinite. But for many tropical matrices N∈MkZ, there are non-negative integers l,m and integer e such that e⊗Nl=Nl+m. If l,m are the smallest non-negative integers such that e⊗Nl=Nl+m, then l is called the pseudo-index of the matrix N and m is called the pseudo-period of the matrix N. If the pseudo-indexes and the pseudo-periods of N and Hii=1,2,…,n are all small, then there may be some potential heuristic attacks. The pseudo-index of tropical matrix increases with the increase of k. Our experiments show that it is feasible to generate N and Hii=1,2,…,n with pseudo-indexes more than k2 (k<30). In A∗H⟶ and B∗H⟶, the entries of A, B are the exponents of Hi. Since A,B∈ℤC, the entries of C and s should not be too large. We recommend fx=xn−1 and(29)C=00…0110…0001…00⋮⋮⋱⋮⋮00…10.Then, the entries ofA, B are in 0,s−1 and the entries of AB are less than ns−12. To resist some potential heuristic attacks, we recommend the parameters s,n,k satisfying k2≥ns−12.If we use the “square-multiply” algorithm to compute the power of tropical matrix, then computingA∗H⟶ requires n2logs+nn−1 tropical matrix multiplications. The numbers of bit operations required for multiplying two tropical matrices of order k are Ok3. So, the total number of bit operations required for calculating A∗H⟶ is Ok3n2logs.The size of secret keya0,a1,…,an−1 is less than nlogs bits. Suppose the entries of the matrices N are in the range 0,T and Hi=∑j=09dij⊗N9 where dij∈0,d. Then, the size of public key U⟶ is less than n2k2logs−1d+9T bits.SelectT=100 and d=1024. Table 2 provides the upper bounds of the size of secrete key and public key for different values of k,n,s such that sn≈280 and k2≈ns−12. And in Table 2, we also compare the running time of the operation A∗H⟶ under different parameters (experimental platform: Intel(R) Core(TM) i7-4700MQ CPU @ 2.40 GHz).Table 2
Performance comparison under some different parameters.
knsUpper bound of sk (bit)Upper bound of pk (kB)Timing ofA∗H⟶ (s)9802806821.79814503807481.46319404808792.372233458010313.210283168011974.316


## 6. Conclusion and Further Research

This paper proposes a new key exchange protocol and a new public key encryption scheme based on multiple exponentiation problem of tropical matrices which can resist all known attacks. Since the generating matrixN of the used commutative subsemirings ZN is hidden and the public key matrices are the product of more than two unknown matrices, the cryptosystems can resist KU attack and generalized KU attack. There is no addition of tropical matrix in A∗H⟶. The attack method proposed by Rudy and Monico does not work for ME problem. As a semigroup action problem derived from semimodules on semirings, ME problem cannot be reduced to hidden subgroup problem in polynomial time. Our cryptosystem can be considered as a potential postquantum cryptosystem.The algebraic properties of pseudo-index and pseudo-period of tropical matrix have not been clearly studied. We can only use enumeration method to find the pseudo-index and pseudo-period of tropical matrix and generate tropical matrices with pseudo-index less than 900. Therefore, in order to prevent potential heuristic attacks, the dimensionn of H⟶ needs to be large n>30. However, this makes the operation efficiency of A∗H⟶ low. If we can generate effectively tropical matrices with large pseudo-index or large pseudo-period, we can choose small n to improve the operation efficiency.Future works worth studying include the following.(1)
Study the properties of pseudo-index and pseudo-period of tropical matrix. If a fast algorithm of generating tropical matrix with large pseudo-index (or pseudo-period) and small order can be found, then the smallern and k can be chosen. This will improve the computational efficiency of our cryptosystem.(2)
Use other commutative tropical matrix semirings instead ofZN. For example, we can design a public key cryptosystem based on ME problem of Jones matrix or Linde–de la Puente matrix. ME problem of commutative matrices over other semirings can also be considered.(3)
ME problem of tropical matrices is a generalization of the discrete logarithm problem. If we regardA∗H⟶ as H⟶A, then ME problem corresponds to discrete logarithm problem, CME problem corresponds to CDH problem, and DME problem corresponds to DDH problem. We believe that other cryptographic applications based on ME problem are also feasible. For example, we can consider the digital signature schemes and identity authentication schemes and other cryptographic applications based on CME assumption or DME assumption, such as [26–28]. However, as we point out previously, the cryptographic system based on ME problem over tropical matrix has no high computational efficiency, since the number of matrices n and the order k of the matrix are large in order to ensure security. It may limit some possible application scenarios.



---

*Source: 1024161-2022-09-09.xml*