# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 4 Concrete Construction for Two-Party LPCP
If \(\mathcal{A}\) can break the ciphertext \(C\) to obtain the plaintext \(m_{b}\), then \(\mathcal{A}\) can obtain the randomness \(r\) by multiplying \(m^{-1}\), the inverse element of \(m\), with the result of \(C\bmod N\). According to the Euler theorem, \(m_{q}^{q-1}\equiv 1\bmod q\) and \(m_{p}^{p-1}\equiv 1\bmod p\). We can obtain \(m_{q}^{q}\equiv m_{q}\bmod q\) and \(m_{p}^{p}\equiv m_{p}\bmod p\). According to the Chinese theorem, the adversary \(\mathcal{A}\) can obtain \(m_{p}\) and \(m_{q}\). Thus, \(\mathcal{A}\) obtains the prime \(p\) by calculating the greatest common divisor \(gcd(N,m-m_{p})\) and obtains the prime \(q\) by calculating the greatest common divisor \(gcd(N,m-m_{q})\). Now the adversary \(\mathcal{A}^{\prime}\) takes \(N\) as input. \(\mathcal{A}^{\prime}\) constructs the ciphertext \(C\) and gives \((C,N)\) to \(\mathcal{A}\) as input. As \(\mathcal{A}\) can break the ciphertext and return the big primes \(p,q\) to \(\mathcal{A}^{\prime}\), \(\mathcal{A}^{\prime}\) can return \(N=pq\) and achieve the prime decomposition, which breaks the factor assumption. \(\mathcal{A}^{\prime}\) can factor the product of big primes \(N=pq\), which breaks the factor assumption. That is, if \(\mathcal{A}\) can break the ciphertext with a non-negligible advantage, \(\mathcal{A}^{\prime}\) can break the factor assumption. Therefore, the encryption scheme is semantically secure in the presence of an eavesdropper. Now the focus of our work is the presentation of the LPCP protocol and a more formal security analysis is required in future work. Eval: Before introducing the evaluation phase, we prove the additive and multiplicative homomorphism of our CRT-based encryption scheme. The purpose of the re-encryption phase is to unify ciphertexts of \(P_{1}\) and \(P_{2}\) into the same ring space \(Z_{T_{2}}\). After the re-encryption, ciphertexts \(C_{1}^{re-enc}\) and \(C_{2}\) are encrypted by the same private key of \(P_{2}\) in the same ring space \(Z_{T_{2}}\), where the additional and multiplicative operations can be performed directly on the ciphertexts. Below, we prove the homomorphism property that the decryption result of \(C_{1}^{re-enc}+C_{2}\equiv r_{1}m_{1}+m_{2}\bmod N_{2}\) and the decryption result of \(C_{1}^{re-enc}*C_{2}\equiv r_{1}m_{1}*m_{2}\bmod N_{2}\). Proof. : \[Enc(r_{1}m_{1})+Enc(m_{2})=C_{1}^{re-enc}+C_{2}\] \[\equiv p_{2}^{-1}p_{2}(C_{1,\mu_{2}}^{q_{2}}+C_{2,\mu_{2}}^{q_{2} })+q_{2}^{-1}q_{2}(C_{1,p_{2}}^{P_{2}}+C_{2,p_{2}}^{P_{2}})+RN_{2}\] \[\bmod T_{2}\] \[Enc(r_{1}m_{1})*Enc(m_{2})=C_{1}^{re-enc}*C_{2}\] \[\equiv(p_{2}^{-1}p_{2})^{2}(C_{1,\mu_{2}}C_{2,\mu_{2}})^{q_{2}}+ (q_{2}^{-1}q_{2})^{2}(C_{1,p_{2}}C_{2,p_{2}})^{p_{2}}+R^{\prime}N_{2}\] \[\bmod T_{2}\] \[Dec(C_{1}^{re-enc}+C_{2})\equiv(m_{1}+m_{2})\bmod N_{2}\] \[Dec(C_{1}^{re-enc}*C_{2})\equiv(m_{1}*m_{2})\bmod N_{2}\]  
After receiving the message \((C_{1}^{re-enc},C_{2},C_{Rec},hash_{2})\), sender \(\mathcal{S}\) checks whether \(\mathcal{H}(C_{1}^{re-enc}||C_{2}||C_{Rec})\) equals the hash value \(hash_{2}\). If verified, \(\mathcal{S}\) continues the evaluation process. Otherwise, \(\mathcal{S}\) outputs \(\bot\) to abort the execution. Then \(\mathcal{S}\) decrypts \(C_{Rec}\) to obtain \(T_{2}\) and partially decrypts \(C_{1}^{re-enc}\) while keeping \(C_{2}\) unchanged. The multiplicative inverse of \(r_{1}\) satisfies \(r_{1}r_{1}^{-1}=1\bmod T_{2}\). As parameter \(N_{2}\) is known to \(\mathcal{R}\), it is easy for \(\mathcal{R}\) to obtain the inverse element \(r_{1}^{-1}\) in the decryption phase. Degree \(deg_{F}\) is the maximum degree of polynomial \(F(x_{1},x_{2})\), and \(deg_{i}\) is the degree of the \(i^{th}\) term of the polynomial. There are two reasons why the random element \(r\) is introduced into the ciphertext. One reason is to prevent \(\mathcal{R}\) from deducing the plaintext \(m_{1}\), reversely referring to \(C_{F}\). The other reason is to unify the degree of the polynomial terms to perform the additive operations.