# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 3 Framework for Two-Party LPCP  
In this section, we introduce the framework for our semi-honest two-party secure computation protocol LPCP. First of all, we define the security model of our two-party LPCP scheme. Considering the following situation, two semi-honest parties \(P_{1}\) and \(P_{2}\) intend to calculate a polynomial function \(F(m_{1},m_{2})\) with inputs \(m_{1}\) and \(m_{2}\), respectively. For convenience, we use \(\mathcal{S}\) to denote sender \(P_{1}\) and \(\mathcal{R}\) to denote receiver \(P_{2}\) in this section. At the beginning of the protocol execution, one party is statically corrupted by the adversary. The corrupted party is allowed to learn as much information as possible, but cannot violate the protocol rules, which meets the definition of a semi-honest adversary. To reduce the time and communication complexity, we abandon those widely used techniques, such as garbled circuits, oblivious transfer and secret sharing. Instead, LPCP implements the Chinese remainder theorem and re-encryption technique to realize additive and multiplicative homomorphism. The main idea of LPCP is that two parties encrypt their plaintexts with different secret keys, initially. Then, one party re-encrypts the other party's ciphertext, transforming both parties' ciphertext under the same secret key, where the computation process can be executed quickly. Finally, both parties decrypt the computed ciphertext to obtain the resulting answer. For concrete proof of the homomorphism, see Proof 4. LPCP consists of five ideal functionalities--the setup functionality \(\mathcal{F}_{Setup}\), the key generation functionality\(\mathcal{F}_{KeyGen}\), the encryption functionality \(\mathcal{F}_{Enc}\), the re-encryption functionality \(\mathcal{F}_{Re-Enc}\), the evaluation functionality \(\mathcal{F}_{Eval}\), and the decryption functionality \(\mathcal{F}_{Dec}\). In \(\mathcal{F}_{Setup}\), two parties jointly decide the security parameter \(\lambda\) and the polynomial function \(F(m_{1},m_{2})\). The polynomial function \(F(m_{1},m_{2})=\sum_{i}a_{i}m_{1}^{b_{i}}m_{2}^{c_{i}}\) takes in \(m_{1}\) and \(m_{2}\), and is expected to output the correct result. All the coefficients \(a_{i}\) and degrees \(b_{i},c_{i}\) of polynomial terms are decided by \(\mathcal{S}\) and \(\mathcal{R}\) in advance. Ideal Functionality \(\mathcal{F}_{Setup}\)  
1. \(\mathcal{S}\) and \(\mathcal{R}\) run \(para\gets Setup(1^{\lambda})\). 2. \(\mathcal{S}\) and \(\mathcal{R}\) decide the polynomial function \(F=\sum_{i=1}^{n}a_{i}m_{1}^{b_{i}}m_{2}^{c_{i}}\). Once the initial parameter \(para\) and the polynomial function are decided, both \(\mathcal{S}\) and \(\mathcal{R}\) begin to generate their private keys according to the parameter \(para\) given in the functionality \(F_{KeyGen}\). It is important to remember that our protocol implements symmetric encryption instead of asymmetric encryption. Therefore, the private key generated should be kept secret by each party respectively. Additionally, the randomness parameter should not be leaked as well. Ideal Functionality \(\mathcal{F}_{KeyGen}\)  
1. \(\mathcal{S}\) and \(\mathcal{R}\) call the parameter \(para\) to generate their secret keys \(sk\) and randomness parameters \(r\) by running \(\{sk,r\}\gets KeyGen(para)\). In the encryption phase, \(\mathcal{S}\) encrypts its message \(m_{1}\) with its private key \(sk_{1}\) and a random element \(r\) generated in \(\mathcal{F}_{KeyGen}\). Receiver \(\mathcal{R}\) encrypts its message in the same way as sender \(\mathcal{S}\), except that \(\mathcal{R}\) does not multiply a random element with its ciphertext. Ideal Functionality \(\mathcal{F}_{Enc}\)  
1. \(\mathcal{S}\) and \(\mathcal{R}\) encrypt their messages respectively by running \(C\gets Enc_{sk}(m,r)\). 2. \(\mathcal{S}\) sends its ciphertext to \(\mathcal{R}\).