# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 4 Concrete Construction for Two-Party LPCP
Enc: In the encryption phase, sender \(\mathcal{S}\) randomly chooses \(r_{1}\in\{0,1\}^{\lambda}\) and \(r_{1}^{\prime},r\in\{0,1\}^{2\lambda}\), then computes  
\[C_{Sen} =f_{pk_{Rnc}}(N_{1}||T_{1}||r) \tag{4}\] \[m_{1,p_{1}} =m_{1}\text{ mod }p_{1}\] \[m_{1,q_{1}} =m_{1}\text{ mod }q_{1}\] \[C_{1,CRT} =p_{1}^{-1}p_{1}m_{1,q_{1}}^{q_{1}}+q_{1}^{-1}q_{1}m_{1,p_{1}}^{ p_{1}}\] \[C_{1} =<r_{1},r_{1}^{\prime}>.<C_{1,CRT},N_{1}>\text{ mod }T_{1}\] \[=(r_{1}(p_{1}^{-1}p_{1}m_{1,q_{1}}^{q_{1}}+q_{1}^{-1}q_{1}m_{1,p_ {1}}^{p_{1}})+r_{1}^{\prime}N_{1})\text{ mod }T_{1}\] \[hash_{1} =\mathcal{H}(C_{Sen}||C_{1})\]  
\(\mathcal{S}\) encrypts his secret modulus \(N_{1}\) and a random element \(r\) with the public key of \(\mathcal{R}\)'s trapdoor permutation. Then \(\mathcal{S}\) implements the Chinese remainder theorem and the Euler's theorem to construct \(C_{1,CRT}\). Here, the purpose of introducing [PERSON]'s theorem is to mess  
Figure 1: The interaction flow chart of LPCP’s framework. The process of \(P_{1}\) is on the left side and the process of \(P_{2}\) is on the right side. up the plaintext information. The ciphertext \(C_{1}\) equals the inner product of randomness tuple \(<r_{1},r_{1}^{\prime}>\) and secret tuple \(<C_{1,CRT},N_{1}>\) modulo \(T_{1}\). In the first communication round, \(\mathcal{S}\) sends \(C=(C_{1},C_{Sen})\) together with the hash value \(hash_{1}\) to \(\mathcal{R}\). On the other hand, receiver \(\mathcal{R}\) randomly chooses \(r_{2}\in\{0,1\}^{\lambda}\) and computes  
\[ \begin{split} C_{Rec}&=f_{pk_{Sen}}(T_{2})\\ m_{2,p_{2}}&=m_{2}\bmod p_{2}\\ m_{2,q_{2}}&=m_{2}\bmod q_{2}\\ C_{2,CRT}&=p_{2}^{-1}p_{2}m_{2,q_{2}}^{q_{2}}+q_{ 2}^{-1}q_{2}m_{2,p_{2}}^{p_{2}}\\ C_{2}&=<1,r_{2}>\cdot<C_{2,CRT},N_{2}>\bmod T_{2}\\ &=(p_{2}^{-1}p_{2}m_{2,q_{2}}^{q_{2}}+q_{2}^{-1}q_{2}m_{2,p_{2}}^ {p_{2}}+r_{2}N_{2})\bmod T_{2}\end{split}  \tag{5}\]  
The encryption process of receiver \(\mathcal{R}\) slightly differs from \(\mathcal{S}\), as the first component of ciphertext \(C_{2,CRT}\) is multiplied by the constant \(1\) instead of a random element. For \(\mathcal{S}\), the existence of the random element \(r_{1}\) is to mask the message for the subsequent process and expand the ciphertext space into \(\mathbb{Z}_{\mathbb{T}_{2}}\). As there is no need for \(C_{2}\) to be masked and re-encrypted, \(\mathcal{R}\) multiplies \(C_{2,CRT}\) by the constant \(1\). To reduce the communication round, receiver \(\mathcal{R}\) does not send out the ciphertext immediately. Instead, receiver \(\mathcal{R}\) delays sending the ciphertext to the re-encryption phase. Re-Enc: After receiving the ciphertext, \(\mathcal{R}\) checks whether \(\mathcal{H}(C_{1}||C_{Sen})\) equals the hash value \(hash_{1}\). If verified, \(\mathcal{R}\) continues the re-encryption process. Otherwise, \(\mathcal{R}\) outputs \(\bot\) to abort the execution. Then \(\mathcal{R}\) decrypts \(C_{Sen}\) to obtain the modulus \(N_{1}\) and randomly chooses \(r_{2}^{\prime}\in_{R}\{0,1\}^{2\lambda}\). \(\mathcal{R}\) re-encrypts \(\mathcal{S}\)'s ciphertext \(C_{1}\) as follows. \[ \begin{split} N_{1}||r&=f_{sk_{Rec}}(C_{Sen})\\ C_{1}^{\prime}&=C_{1}\bmod N_{1}\\ C_{1,q_{2}}&=C_{1}^{\prime}\bmod q_{2}\\ C_{1,p_{2}}&=C_{1}^{\prime}\bmod p_{2}\\ C_{1}^{re-enc}&=(p_{2}^{-1}p_{2}C_{1,q_{2}}^{2}+q_{ 2}^{-1}q_{2}C_{1,p_{2}}^{p_{2}}+r_{2}^{\prime}N_{2})\bmod T_{2}\\ hash_{2}&=\mathcal{H}(C_{Rec}||C_{2}||C_{1}^{re-enc}) \end{split}  \tag{6}\]  
As a result, the ciphertext \(C_{1}^{\prime}\) is equivalent to \(r_{1}m_{1}\bmod N_{1}\) according to the Chinese remainder theorem and [PERSON]'s theorem. The re-encryption operation transforms \(\mathcal{S}\)'s ciphertext space into \(\mathcal{R}\)'s ciphertext space \(T_{2}\), which lays a foundation for the next evaluation phase. In the second communication round, receiver \(\mathcal{R}\) sends ciphertext \((C_{1}^{re-enc},C_{2})\) with the hash signature \(hash_{2}\) back to \(\mathcal{S}\).