# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 3 Framework for Two-Party LPCP
As mentioned above, sender \(\mathcal{S}\) and receiver \(\mathcal{R}\) encrypt their messages with different private keys and different randomness tuples, which results in their ciphertexts being in two distinct ciphertext spaces. Direct addition and multiplication on such two ciphertexts result in a wrong answer. That is why we introduce the re-encryption functionality \(\mathcal{F}_{Re-Encryption}\). The re-encryption functionality aims to make sure that _matlcalS_'s ciphertext is correctly calculated with receiver \(\mathcal{R}\)'s ciphertext without leaking secret information. Ideal Functionality \(\mathcal{F}_{Re-Enc}\)  
1. Receiver \(\mathcal{R}\) receives the original ciphertext \(C\) from sender \(\mathcal{S}\). 2. Receiver \(\mathcal{R}\) partially decrypts the ciphertext \(C\) in order to obtain the intermediate ciphertext \(C_{intermediate}\). Receiver \(\mathcal{R}\) re-encrypts the intermediate ciphertext \(C_{intermediate}\) to obtain the sender \(\mathcal{S}\)'s ciphertext under the receiver \(\mathcal{R}\)'s secret key by running \(C^{\prime}\gets Re-Enc_{sk}(C_{intermediate})\). 4 Receiver \(\mathcal{R}\) sends back the re-encryption result \(C^{\prime}\) to sender \(\mathcal{S}\). The evaluation functionality is the key step where sender \(\mathcal{S}\) finishes the calculation. The ciphertexts are transformed into the same ciphertext space; however, with different polynomial degrees. It is necessary for sender \(\mathcal{S}\) to unify the degree of every term in the polynomial before the evaluation. After that, sender \(\mathcal{S}\) calculates the sum of every polynomial term, finishing the evaluation step. Ideal Functionality \(\mathcal{F}_{Eval}\)  
1. Sender \(\mathcal{S}\) receives \(\mathcal{R}\)'s ciphertext \(C\) together with the re-encryption ciphertext \(C^{\prime}\) and reduces the initial randomness \(r\) from its re-encryption ciphertext. 2. Sender \(\mathcal{S}\) carries out the computation function \(C_{F}\gets Eval(C,C^{\prime})\). 3. Sender \(\mathcal{S}\) transfers \(C_{F}\) to receiver \(\mathcal{R}\). In the end, we reach the final step--the decryption functionality. Receiver \(\mathcal{R}\), who owns the private key \(sk_{2}\), implements the decryption and sends the output back to \(\mathcal{S}\). 1. Receiver \(\mathcal{R}\) runs the decryption functionality to obtain \(Output\gets Dec_{sk,r}(C_{F})\). 2. Receiver \(\mathcal{R}\) shares the \(Output\) to \(\mathcal{S}\). In a nutshell, sender \(\mathcal{S}\) appends a random integer \(r\) to its message \(m_{1}\) and encrypts them with \(\mathcal{S}\)'s private key. Receiver \(\mathcal{R}\) encrypts its message \(m_{2}\) with \(\mathcal{R}\)'s private key. Up to now, the two ciphertexts from \(\mathcal{S}\) and \(\mathcal{R}\) lie in the different ciphertext space. Then, \(\mathcal{S}\) sends its ciphertext to \(\mathcal{R}\). \(\mathcal{R}\) re-encrypts \(\mathcal{S}\)'s ciphertext with \(\mathcal{R}\)'s private key so that both \(\mathcal{S}\)'s ciphertext and \(\mathcal{R}\)'s ciphertext lie in the same ciphertext space, where the addition and multiplication operations can be performed directly. After that, \(\mathcal{R}\) sends the re-encrypted ciphertexts to \(\mathcal{S}\). It is \(\mathcal{S}\)'s turn to eliminate the random integer \(r\) introduced by itself and carry out the polynomial calculation. At last, \(\mathcal{S}\) sends the calculation result back to \(\mathcal{R}\), which can only be decrypted by \(\mathcal{R}\)'s private key. Once \(\mathcal{R}\) finishes the decryption, it shares the output with \(\mathcal{S}\). Throughout the process, the privacy of the inputs and intermediate results are kept secret, which fulfills the goal of 2 PC.