# Public-Key Cryptography Based on Tropical Circular Matrices
## Appendix B An Example of Solving TMCAP with Small Parameters  
We choose the parameters \(k=3\) and \(s=t=23\) and the entries of the matrices in \([0,100]\). The public matrix \(Y\) is as follows:  
\[Y=\begin{pmatrix}81&24&82\\ 5&52&98\\ 3&2&69\end{pmatrix},\]  
[PERSON] selects at random two \(t\)-circular matrices \(P_{1},Q_{1}\) as follows:  
\[P_{1}=\left[0\,8\,31\right]^{23},\;Q_{1}=\left[68\,0\,6\right]^{23}.\]  
[PERSON] computes \(K_{a}=P_{1}YQ_{1}\). She sends the matrix \(K_{a}\) to [PERSON].  
\[K_{a}=\begin{pmatrix}24&63&53\\ 32&34&28\\ 2&32&26\end{pmatrix},\]  
The attacker knows \(k,t,Y\) and obtains \(K_{a}\). They try to find \(P_{1}\) and \(Q_{1}\).  
Let \(P_{1}=\left[x_{0}\,x_{1}\,x_{2}\right]^{23}\) and \(Q_{1}=\left[y_{0}\,y_{1}\,y_{2}\right]^{23}\). Then,  
\[\left[x_{0}\,x_{1}\,x_{2}\right]^{23}\begin{pmatrix}81&24&82\\ 5&52&98\\ 3&2&69\end{pmatrix}\left[y_{0}\,y_{1}\,y_{2}\right]^{23}=\begin{pmatrix}24&63 &53\\ 32&34&28\\ 2&32&26\end{pmatrix}(\sharp).\]  
From it, they can obtain the tropical linear equations,\[\left\{\begin{array}{lcl}81x_{0}y_{0}\oplus 24x_{0}y_{1}\oplus 82x_{0}y_{2}\oplus 2 6x_{1}y_{0}\oplus 25x_{1}y_{1}\oplus 92x_{1}y_{2}\oplus 28x_{2}y_{0}\oplus 75x_{2}y_{1} \oplus 121x_{2}y_{2}&=&24\\ 24x_{0}y_{0}\oplus 82x_{0}y_{1}\oplus 124x_{0}y_{2}\oplus 25x_{1}y_{0}\oplus 92x_{1}y_{1} \oplus 49x_{1}y_{2}\oplus 75x_{2}y_{0}\oplus 121x_{2}y_{1}\oplus 51x_{2}y_{2}&=&63\\ 82x_{0}y_{0}\oplus 124x_{0}y_{1}\oplus 47x_{0}y_{2}\oplus 92x_{1}y_{0}\oplus 49x_{1}y_{1} \oplus 48x_{1}y_{2}\oplus 121x_{2}y_{0}\oplus 51x_{2}y_{1}\oplus 98x_{2}y_{2}&=&53\\ 5x_{0}y_{0}\oplus 52x_{0}y_{1}\oplus 98x_{0}y_{2}\oplus 81x_{1}y_{0}\oplus 24x_{1}y_{1 }\oplus 82x_{1}y_{2}\oplus 26x_{2}y_{0}\oplus 25x_{2}y_{1}\oplus 92x_{2}y_{2}&=&32\\ 52x_{0}y_{0}\oplus 98x_{0}y_{1}\oplus 28x_{0}y_{2}\oplus 24x_{1}y_{0}\oplus 82x_{1}y_{ 1}\oplus 124x_{1}y_{2}\oplus 25x_{2}y_{0}\oplus 92x_{2}y_{1}\oplus 49x_{2}y_{2}&=&34\\ 98x_{0}y_{0}\oplus 28x_{0}y_{1}\oplus 75x_{0}y_{2}\oplus 82x_{1}y_{0}\oplus 124x_{1}y_{ 1}\oplus 47x_{1}y_{2}\oplus 92x_{2}y_{0}\oplus 49x_{2}y_{1}\oplus 48x_{2}y_{2}&=&28\\ 3x_{0}y_{0}\oplus 2x_{0}y_{1}\oplus 69x_{0}y_{2}\oplus 5x_{1}y_{0}\oplus 52x_{1}y_{ 1}\oplus 98x_{1}y_{2}\oplus 82x_{2}y_{0}\oplus 24x_{2}y_{1}\oplus 82x_{2}y_{2}&=&2 \\ 2x_{0}y_{0}\oplus 69x_{0}y_{1}\oplus 26x_{0}y_{2}\oplus 52x_{1}y_{0}\oplus 98x_{1}y_{ 1}\oplus 28x_{1}y_{2}\oplus 24x_{2}y_{0}\oplus 82x_{2}y_{1}\oplus 125x_{2}y_{2}&=&32\\ 69x_{0}y_{0}\oplus 26x_{0}y_{1}\oplus 25x_{0}y_{2}\oplus 98x_{1}y_{0}\oplus 28x_{1}y _{1}\oplus 75x_{1}y_{2}\oplus 82x_{2}y_{0}\oplus 125x_{2}y_{1}\oplus 47x_{2}y_{2}&=&26 \end{array}\right.\]  
where \(ax_{i}y_{j}\) denotes \(a\otimes x_{i}\otimes y_{j}\). After solving the tropical linear equations, the attacker can obtain a solution, for example:  
\[\left\{\begin{array}{lcl}x_{0}\otimes y_{0}&=&39&(\text{A1})\\ x_{0}\otimes y_{1}&=&0&(\text{A2})\\ x_{0}\otimes y_{2}&=&6&(\text{A3})\\ x_{1}\otimes y_{0}&=&38&(\text{A4})\\ x_{1}\otimes y_{1}&=&8&(\text{A5})\\ x_{1}\otimes y_{2}&=&14&(\text{A6})\\ x_{2}\otimes y_{0}&=&9&(\text{A7})\\ x_{2}\otimes y_{1}&=&7&(\text{A8})\\ x_{2}\otimes y_{2}&=&12&(\text{A9})\end{array}\right.\]  
where \"+\" denotes the ordinary addition.  
It is easy to verify that (A1)-(A6) have no solution. (A2)-(A7) also have no solution.  
The attacker keeps looking for a combination that may have a solution until they find a combination that has a solution. For example, they find that combinations (A1)-(A3), (A5), (A6), and (A8) have a solution \(x_{0}=0,x_{1}=8,x_{2}=7,y_{0}=39,y_{1}=0,y_{2}=6\). The attacker substitutes this solution into (\(\sharp\)) to verify that it is a true solution of (\(\sharp\)). An attacker can find a solution by trying, at most, \(\binom{9}{6}\) cases.