# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 5 Security Proof
### Privacy  
We give the privacy proof of the 2 PC LPCP protocol by simulation. First, we consider the case of sender \(\mathcal{S}\) being corrupted by the semi-honest adversary \(\mathcal{A}_{1}\). The adversary \(\mathcal{A}_{1}\) obtains access to all the input and output of \(\mathcal{S}\), including \(\mathcal{S}\)'s security parameter \(1^{\lambda}\), the input message \(m_{1}\), the prime tuple \((p_{1},q_{1},s_{1})\), the randomness tuple, the polynomial function \(F(m_{1},m_{2})\) and the ciphertexts received. Receiver \(\mathcal{R}\) sends the ciphertexts to the adversary \(\mathcal{A}_{1}\) in the second communication round and fourth communication round. The input ciphertexts are simulated as follows:  
1. In the second round simulation, \(\mathcal{S}\) receives the ciphertext \((C_{1}^{re-enc},C_{2})\). 2. In the fourth round simulation, \(\mathcal{S}\) receives the plaintext \(Output\). Below, we prove that the honest sender \(\mathcal{S}\) cannot distinguish its simulated view with its real execution view. 1. \(\mathcal{H}^{\prime}_{real}\): This hybrid is the same as the real-world execution. 2. \(\mathcal{H}^{\prime}_{1}\): This hybrid is the same as \(\mathcal{H}^{\prime}_{real}\), except we change the output from \(Output\) to \(Output^{Sim}\). \(\mathcal{R}\) randomly chooses \(Output^{Sim}\in\{0,1\}^{2\lambda}\). According to Theorem 2 and the reason that \(\mathcal{S}\) does not know the modulus \(N_{2}\) for decryption, \(\mathcal{S}\) cannot distinguish the real output \(Output\) from the simulated output \(Output^{Sim}\). 3. \(\mathcal{H}^{\prime}_{2}\): This hybrid is the same as \(\mathcal{H}^{\prime}_{1}\), except we change the ciphertext from \((C_{1}^{re-enc},C_{2})\) to \((C_{1}^{re-encSim},C_{2}^{Sim})\). \(\mathcal{R}\) randomly chooses the ciphertext \(C_{1}^{re-encSim}\leq T\) and \(C_{2}^{Sim}\leq T\). As \(\mathcal{S}\) has no information about \(\mathcal{R}\)'s value \(m_{2},N_{2},r_{2}\), \(\mathcal{S}\) cannot distinguish the real ciphertext \(C_{2}^{Sim}\) from the simulated ciphertext \(C_{1}^{2}\). According to Theorem 1, \(\mathcal{S}\) cannot distinguish the real re-encryption ciphertext \(C_{1}^{re-enc}\) from the simulated re-encryption ciphertext \(C_{1}^{re-encSim}\). The hybrid model \(\mathcal{H}^{\prime}_{real}\) is statistically indistinguishable from the hybrid model \(\mathcal{H}^{\prime}_{2}\), where \(\mathcal{H}^{\prime}_{real}\) is the real-world view of \(\mathcal{S}\), and \(\mathcal{H}^{\prime}_{2}\) is the ideal world view of \(\mathcal{S}\). Therefore, the 2 PC LPCP protocol is secure when \(\mathcal{S}\) is corrupted. Secondly, we consider the case of \(\mathcal{R}\) being corrupted by the semi-honest adversary \(\mathcal{A}_{2}\). The adversary \(\mathcal{A}_{2}\) gets access to all the input and output of receiver \(\mathcal{R}\), including \(\mathcal{R}\)'s security parameter \(1^{\lambda}\), the input message \(m_{2}\), the prime tuple \((p_{2},q_{2},s_{2})\), the randomness tuple, the polynomial function \(F(m_{1},m_{2})\) and the ciphertexts received. The adversary \(\mathcal{A}_{2}\) receives ciphertexts in the first and third communication round. 1. In the first round, \(\mathcal{R}\) receives the ciphertext \(C_{1}\). 2. In the third round, \(\mathcal{R}\) receives the ciphertext \(C_{F}\). Below, we prove that the semi-honest sender \(\mathcal{R}\) can not distinguish the simulated view with the real execution view. 1. \(\mathcal{H}_{Real}\): This hybrid model is the same as the real-world execution. 2. \(\mathcal{H}_{1}\): This hybrid model is the same as \(\mathcal{H}_{real}\), except we change the ciphertext \((C_{1}^{re-enc},C_{2})\) to the randomly simulated ciphertexts \((C_{1}^{re-enc},C_{2}^{Sim})\). When \(\mathcal{S}\) simulates the ciphertext \((C_{1}^{re-enc},C_{2})\), \(\mathcal{S}\) chooses a random element \(C_{F}^{Sim}\in\{0,1\}^{3\lambda}\) and sends \(C_{F}^{Sim}\) to \(\mathcal{R}\).