# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 4 Concrete Construction for Two-Party LPCP  
In this section, we give a detailed description of our two-party secure computation protocol LPCP. For three-party and more parties MPC cases, see Section 6. In the setting of two-party LPCP, there are two semi-honest parties \(P_{1}\) and \(P_{2}\), with inputs \(m_{1}\) and \(m_{2}\), respectively. Both parties intend to compute a polynomial function \(F(m_{1},m_{2})=\sum_{i=1}^{n}a_{i}m_{1}^{b_{i}}m_{2}^{c_{i}}\) without leaking any information of their input. Here, we assume the communication channel and both parties' identifications are authenticated, so they do not need additional negotiations. For convenience, we use \(\mathcal{S}\) to denote sender \(P_{1}\) and \(\mathcal{R}\) to denote receiver \(P_{2}\). As Section 3 shows, our protocol consists of six phases--the Setup phase, KeyGen phase, Enc phase, Re-Enc phase, Eval phase, and Dec phase in four communication rounds. Figure 1 shows the sketch map of our protocol. Setup: At the beginning of the protocol, \(P_{1}\) and \(P_{2}\) decide the security parameter \(1^{\lambda}\). If party \(P_{i}\) has not generated the one-way trapdoor permutation function, \(P_{i}\) runs the one-way trapdoor permutation generation algorithm to obtain a one-way trapdoor permutation function pair \((f,f^{-1})\) on \(\{0,1\}^{2\lambda}\). We denote the one-way trapdoor permutation function key pair of sender \(\mathcal{S}\) as \((sk_{Sen},pk_{Sen})\) and the key pair of receiver \(\mathcal{R}\) as \((sk_{Rec},pk_{Rec})\). If both parties have generated their one-way trapdoor permutation function, they can skip the Once the security parameter length \(\lambda\) is decided, all the parameters can be generated without this communication. For this reason, we can pre-process the setup phase as follows. Both parties pre-process the generation of parameters while they are free. In this way, we can reduce one communication round to optimize the setup phase. As a result, when the request arrives, both parties choose the corresponding security parameters from the parameter library and run the protocol as soon as possible. KeyGen: In the key generation phase, both parties initialize an integer \(N_{0}\in\{0,1\}^{2\lambda}\). The message space \(\mathcal{M}\) is set to be \(\mathbb{Z}_{N_{0}}^{*}\) where \(N_{0}^{\prime}=\{0,1\}^{\lambda-1}\). For each party \(P_{i}\) where \(i=0\) or \(i=1\), three primes \(p_{i},q_{i},s_{i}\) are randomly and independently chosen such that \(|p_{i}|=|q_{i}|=|s_{i}|=\lambda\). \(P_{i}\) computes \(N_{i}=p_{i}q_{i}\) satisfying \(N_{i}\geq N_{0}\) and \(T_{i}=p_{i}q_{i}s_{i}\). \(p_{i}^{-1}\) is the multiplicative inverse element of \(p_{i}\) modulo \(q_{i}\) such that \(p_{i}^{-1}p_{i}\equiv 1\) mod \(q_{i}\) and \(q_{i}^{-1}\) is the multiplicative inverse element of \(q_{i}\) modulo \(p_{i}\) such that \(q_{i}^{-1}q_{i}\equiv 1\) mod \(p_{i}\). Each party holds \((p_{i},q_{i},s_{i},N_{i},T_{i})\), where \(p_{i},q_{i},N_{i},s_{i}\) remain secret, while \(T_{i}\) is public. As LPC only involves symmetric encryption, there is no public key. This generation of big primes \(p_{i},q_{i},s_{i}\) and the multiplicative inverse elements \(p_{i}^{-1},q_{i}^{-1}\) can be pre-processed before the protocol when the parties are free. When the secure computation request comes, the parties can quickly choose a tuple of pre-generated parameters and consume it in the following execution. It must be ensured that every secure computation consumes a differently new tuple of \((p_{i},q_{i},s_{i})\).