# Public-Key Cryptography Based on Tropical Circular Matrices
## 3 Public-Key Cryptography Using Tropical \(T\)-Circular Matrices
### Public-Key Encryption Scheme Based on Tropical Circular Matrices  
**Cryptosystem 1**. :
1. **Key generation:** Let \(k,s,t\) be three positive integers. Let \(P_{1}\in C_{k}^{s}\), \(Q_{1}\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}\). \(k,s,t,Y\) are public. [PERSON]'s public key is \(K_{a}\). [PERSON]'s secret key is \(P_{1},Q_{1}\). 2. **Encryption:** [PERSON] wants to send a message \(M\in M_{k}(\mathbb{Z})\) to [PERSON]. 1. [PERSON] chooses at random \(P_{2}\in C_{k}^{s}\), \(Q_{2}\in C_{k}^{t}\) and computes \(R=P_{2}YQ_{2}\) as a part of the ciphertext. 2. [PERSON] computes \(S=M+P_{2}K_{a}Q_{2}\) as the rest of the ciphertext, where \"+\" is the ordinary integer matrix addition. 3. [PERSON] sends the ciphertext \((R,S)\) to [PERSON]. 3. **Decryption:** [PERSON] receives the ciphertext \((R,S)\) and tries to decrypt it. 1. Using her secret key \(P_{1},Q_{1}\), [PERSON] computes \(T=P_{1}RQ_{1}\). 2. [PERSON] computes \(S-T\), where \"\(-\)\" is the ordinary integer matrix subtraction. Since  
\[ \begin{array}{ll}S-T&=M+P_{2}K_{a}Q_{2}-P_{1}RQ_{1}\\ &=M+P_{2}(P_{1}YQ_{1})Q_{2}-P_{1}(P_{2}YQ_{2})Q_{1}\\ &=M+P_{2}P_{1}YQ_{1}Q_{2}-P_{1}P_{2}YQ_{2}Q_{1}\\ &=M+P_{1}P_{2}YQ_{1}Q_{2}-P_{1}P_{2}YQ_{1}Q_{2}\\ &=M,\end{array} \]  
[PERSON] obtains the plaintext messages \(M\). Definition 5: Let \(k,s,t\) be three positive integers. Let \(P_{1},P_{2}\in\mathbb{C}_{k}^{s}\), \(Q_{1},Q_{2}\in C_{k}^{t}\) and \(Y,E\in M_{k}(\mathcal{Z})\backslash(\mathbb{C}_{k}^{s}\cup C_{k}^{t})\). Suppose that \(K_{a}=P_{1}YQ_{1}\) and \(K_{b}=P_{2}YQ_{2}\). The decisional two-side tropical circular matrix action problem (DTCMAP) is to decide whether \(E=P_{1}P_{2}YQ_{1}Q_{2}\), given \(Y,K_{a},K_{b},E\). Proposition 3: An algorithm that solves CTCMAP can be used to solve DTCMAP. Theorem 2: An algorithm that solves DTCMAP can be used to decide the validity of the ciphertexts of Cryptosystem 1, and an algorithm that decides the validity of the ciphertexts of Cryptosystem 1 can be used to solve DTCMAP. Proof of Theorem 2: Suppose first that the algorithm \(\mathcal{A}_{1}\) can decide whether a decryption of Cryptosystem 1 is correct. In other words, when given the inputs \(Y,K_{a},(R,S),M\), the algorithm \(\mathcal{A}_{1}\) outputs \"yes\" if \(M\) is the decryption of \((R,S)\) and outputs \"no\" otherwise. Let us use \(\mathcal{A}_{1}\) to solve the decisional two-side tropical circular matrix action problem. Suppose you are given \(Y\), \(K_{a}(=P_{1}YQ_{1})\), \(K_{b}(=P_{2}YQ_{2})\) and \(E\), and you want to decide whether or not \(E=P_{1}P_{2}YQ_{1}Q_{2}\). Let \(K_{a}\) be the public key and \(R=K_{b}\) be the first part of the ciphertext. Moreover, let \(S=E\) be the second part of the ciphertext and \(M=0_{k\times k}\) be the zero matrix in \(M_{k}(\mathcal{Z})\). Input all of these into \(\mathcal{A}_{1}\). Note that, in the present setup, \(P_{1},Q_{1}\) are the secret keys. The correct decryption of \((R,S)\) is \(S-P_{1}RQ_{1}=E-P_{1}P_{2}YQ_{1}Q_{2}\). Therefore, \(\mathcal{A}_{1}\) outputs \"yes\" exactly when \(M=0\) is the same as \(E-P_{1}P_{2}YQ_{1}Q_{2}\), namely, when \(E=P_{1}P_{2}YQ_{1}Q_{2}\). This solves DTCMAP. Conversely, suppose an algorithm \(\mathcal{A}_{2}\) can solve DTCMAP. This means that if you give \(\mathcal{A}_{2}\) inputs \(Y\), \(K_{a}(=P_{1}YQ_{1})\), \(K_{b}(=P_{2}YQ_{2})\) and \(E\), then \(\mathcal{A}_{2}\) outputs \"yes\" if \(E=P_{1}P_{2}YQ_{1}Q_{2}\) and outputs \"no\" if not. Let \(M\) be the claimed decryption of the ciphertext \((R,S)\). Input the public key \(K_{a}\) and input \(R=P_{2}YQ_{2}\) as \(K_{b}\). Input \(S-M\) as \(E\). Note that \(M\) is the correct plaintext for the ciphertext \((R,S)\) if and only if \(M=S-P_{1}RQ_{1}=S-P_{1}P_{2}YQ_{1}Q_{2}\), which happens if and only if \(S-M=P_{1}P_{2}YQ_{1}Q_{2}\). Therefore, \(M\) is the correct plaintext if and only if \(E=P_{1}P_{2}YQ_{1}Q_{2}\). Therefore, with these inputs, \(\mathcal{A}_{2}\) outputs \"yes\" exactly when \(M\) is the correct plaintext.