# Public-Key Cryptography Based on Tropical Circular Matrices
## 4 Security and Parameter Selection  
Through Theorem 1, Proposition 3, and Theorem 2, an efficient algorithm for solving the two-side tropical circular matrix action problem can be used to attack Protocol 1 and Cryptosystem 1.  
Proposition 4: TCMAP can be reduced to the problem of solving a tropical nonlinear system of equations.  
Proof of Proposition 4: Let \(P\in\mathbb{C}_{k}^{s}\), \(Q\in\mathbb{C}_{k}^{t}\) and \(Y\in M_{k}(\mathcal{Z})\backslash(\mathbb{C}_{k}^{s}\cup\mathbb{C}_{k}^{t})\). Suppose that \(N=PYQ\). Now, we can try to find two matrices, \(P\in S_{1}\) and \(Q\in S_{2}\), such that \(N=PYQ\), given \(N\) and \(Y\).  
Suppose that \(P=\left[x_{0},x_{1},\cdots,x_{k-1}\right]^{s}\) and \(Q=\left[y_{0},y_{1},\cdots,y_{k-1}\right]^{t}\). Then,  
\[\left[x_{0},x_{1},\cdots,x_{k-1}\right]^{s}\cdot Y\cdot\left[y_{0},y_{1}, \cdots,y_{k-1}\right]^{t}=N\]Since \(Y\) and \(N\) are known, we obtain a tropical nonlinear system of equations about \(x_{0},x_{1},\cdots,x_{k-1},y_{0},y_{1},\cdots,y_{k-1}\) with \(2k\) unknowns and \(k^{2}\) equations. \(\square\)  
As we know, the problem of solving a tropical nonlinear system of equations is usually NP-hard [24]. We present an algorithm for solving the two-side tropical circular matrix action problem with exponential computational complexity.  
**Proposition 5**.: _There exists an algorithm for solving the two-side tropical circular matrix action problem with computational complexity \(O\left(k^{4}+6k^{3}\cdot\binom{k^{2}}{2k}\right)\)._  
Proof of Proposition 5.: With Proposition 4, we obtain a tropical nonlinear system of equations about \(x_{0},x_{1},\cdots,y_{k-1}\) with \(2k\) unknowns and \(k^{2}\) equations. Note that every term of the equations is the form of \(x_{i}y_{j}\) (\(i,j=0,1,\cdots,k-1\)). Denote \(z_{0}=x_{0}y_{0}\), \(z_{1}=x_{0}y_{1},\cdots,z_{k^{2}}=x_{k-1}y_{k-1}\). Then, we obtain a tropical linear system of equations with \(k^{2}\) unknowns \(z_{i}\) and \(k^{2}\) equations.  
After solving the tropical linear system of equations of \(z_{i}\), we can obtain a system of nonlinear equations  
\[x_{0}y_{0}=z_{0},x_{0}y_{1}=z_{1},\cdots,x_{k-1}y_{k-1}=z_{k^{2}}\]  
Since multiplication in tropical algebra is an ordinary addition, it is actually a system of linear equations over an integer ring. The linear equations have \(2k\) unknowns and \(k^{2}\) equations. Generally, the system of linear equations has no solution. However, if the \(2k\) equations in these \(k^{2}\) equations have a solution, it is possible to find \(x_{0},x_{1},\cdots,y_{k-1}\) such that  
\[[x_{0},x_{1},\cdots,x_{k-1}]^{s}\cdot Y\cdot[y_{0},y_{1},\cdots,y_{k-1}]^{t}=N.\]  
Using the algorithm in [33], the complexity of solving the tropical linear system of equations with \(k^{2}\) unknowns \(z_{i}\) and \(k^{2}\) equations is \(O(k^{4})\). The number of possible choices for selecting \(2k\) equations from \(k^{2}\) equations is \(\binom{k^{2}}{2k}\). The complexity of solving integer linear equations with \(2k\) equations and \(2k\) unknowns is \(O((2k)^{3})\). Therefore, the computational complexity of the above algorithm is \(O\left(k^{4}+6k^{3}\cdot\binom{k^{2}}{2k}\right)\). \(\square\)  
An example of solving TMCAP with small parameters is given in Appendix B.