# Public-Key Cryptography Based on Tropical Circular Matrices
## 3 Public-Key Cryptography Using Tropical \(T\)-Circular Matrices  
### Key Exchange Protocol Based on Tropical Circular Matrices  
**Definition 3**. : _Let \(s\) and \(t\) be two integers. Let \(P\in C_{k}^{s}\), \(Q\in C_{k^{\prime}}^{t}\), and \(Y\in M_{k}(\mathcal{Z})\backslash(C_{k}^{s}\cup C_{k}^{t})\). Suppose that \(N=PYQ\). The two-side tropical circular matrix action problem (TCMAP) is to find two matrices \(P\in C_{k}^{s}\), \(Q\in C_{k}^{t}\) such that \(N=PYQ\), given the matrices \(N\) and \(Y\)._  
**Protocol 1**. : _Let \(k,s,t\) be three positive integers. Let \(Y\in M_{k}(\mathcal{Z})\backslash(C_{k}^{s}\cup C_{k}^{t})\). In addition, \(k,s,t\) and \(Y\) are public._  
1. _[PERSON] selects at random two matrices_ \(P_{1}\in C_{k}^{s}\) _and_ \(Q_{1}\in C_{k}^{t}\)_, and computes_ \(K_{a}=P_{1}YQ_{1}\)_. In addition, she sends to [PERSON] the matrix_ \(K_{a}\)_._
2. _[PERSON] selects at random two matrices_ \(P_{2}\in C_{k}^{s}\) _and_ \(Q_{2}\in C_{k}^{t}\)_, and computes_ \(K_{b}=P_{2}YQ_{2}\)_. He sends to [PERSON] the vector_ \(K_{b}\)_._
3. _[PERSON] computes_ \(K=P_{1}K_{b}Q_{1}\)_. In addition, [PERSON] computes_ \(K=P_{2}K_{a}Q_{2}\)_. Since_ \(C_{k}^{s}\) _and_ \(C_{k}^{t}\) _are commutative sub-semirings of_ \(M_{k}(\mathcal{Z})\)_, we have_ \(P_{1}P_{2}=P_{2}P_{1}\)_,_ \(Q_{1}Q_{2}=Q_{2}Q_{1}\) _and_ \(P_{1}K_{b}Q_{1}=P_{1}(P_{2}YQ_{2})Q_{1}=(P_{1}P_{2})Y(Q_{2}Q_{1})=(P_{2}P_{1}YQ _{1})Q_{2}=P_{2}K_{a}Q_{2}\)_._  
_Then, [PERSON] and [PERSON] share a secret key \(K\)._  
**Definition 4**. : _Let \(k,s,t\) be three positive integers. Let \(P_{1},P_{2}\in C_{k^{\prime}}^{s}\), \(Q_{1},Q_{2}\in C_{k}^{t}\) and \(Y\in M_{k}(\mathcal{Z})\backslash(C_{k}^{s}\cup C_{k}^{t})\). Suppose that \(K_{a}=P_{1}YQ_{1}\) and \(K_{b}=P_{2}YQ_{2}\). The computational two-side tropical circular matrix action problem (CTCMAP) is to find a matrix \(K\in M_{k}(\mathcal{Z})\) such that \(K=P_{1}P_{2}YQ_{1}Q_{2}\), given the matrices \(K_{a},K_{b}\) and \(Y\)._  
**Proposition 2**. : _An algorithm that solves TCMAP can be used to solve CTCMAP._  
**Theorem 1**. : _Finding the common secret key from the public information of Protocol 1 is equivalent to solving CTCMAP._  
We give a practical example of Protocol 1 with small parameters in Appendix A. **Remark 1**. : _Protocol 1 is simplified. It can only resist passive attacks, but not active attacks, such as intruder-in-the-middle attacks. To avoid these attacks, it is desirable to have a procedure that authenticates [PERSON] and [PERSON]'s identities to each other while the key is being formed. A standard way to stop an intruder-in-the-middle attack is the station-to-station (STS) protocol, which uses digital signatures._  
_The extended protocol makes use of certificates that, as usual, are signed by a TA (trusted authority). Each user U will have a signature scheme with a verification algorithm \(\mathrm{Ver}_{\mathrm{U}}\) and a signing algorithm \(\mathrm{Sig}_{\mathrm{U}}\). The TA also has a signature scheme with a public verification algorithm \(\mathrm{Ver}_{\mathrm{TA}}\). Each user U has a certificate_  
\[\mathbf{Cert}(\mathrm{U})=(ID(U),\mathrm{Ver}_{\mathrm{U}},\mathrm{Sig}_{ \mathrm{TA}}(ID(U),\mathrm{Ver}_{\mathrm{U}})),\]  
_where \(ID(U)\) is certain identification information for U._  
**Protocol 2**. : _The public domain parameters consist of \(k,s,t\) and \(Y\) as Protocol 1._  
(1) _[PERSON] selects at random two matrices_ \(P_{1}\in C_{k}^{s}\) _and_ \(Q_{1}\in C_{k}^{t}\)_, and computes_ \(K_{a}=P_{1}YQ_{1}\)_. She sends_ \(\mathbf{Cert}(A)\) _and_ \(K_{a}\) _to [PERSON]._  
(2) _[PERSON] selects at random two matrices_ \(P_{2}\in C_{k}^{s}\) _and_ \(Q_{2}\in C_{k}^{t}\)_, and computes_  
\[K_{b}=P_{2}YQ_{2},\ K=P_{2}K_{a}Q_{2}=P_{2}P_{1}YQ_{1}Q_{2},\ y_{b}=\mathrm{ sig}_{\mathrm{B}}(\mathrm{ID}(\mathrm{A})||K_{b}||K_{a}).\]  
_Then, [PERSON] sends_ \(\mathbf{Cert}(B)\)_,_ \(K_{b}\) _and_ \(y_{b}\) _to [PERSON]._  
(3) _[PERSON] verifies_ \(y_{b}\) _using_ \(\mathrm{Ver}_{\mathrm{B}}\)_.