# LPCP: An efficient Privacy-Preserving Protocol for Polynomial Calculation Based on CRT
## 7 Mobile Device Distance Measurement Applications  
In this section, we present a mobile device distance measurement application based on LPCP. Nowadays, many mobile phone applications (APP) services are built on the location based service (LBS) [24; 25]. For example, when users want to search the nearest take-out restaurant for dinner or they want to make friends with the stranger within a three-kilometer range on dating software, they need to upload their location information to APP servers. However, this uploading location information may reveal their location or even reveal their home address. Therefore, it is necessary to introduce location privacy techniques into those LBS-based APPs. Multiparty secure computation techniques can solve the location privacy problems above. However, it takes too much time, from seconds to minutes, for traditional MPC protocols to be executed on mobile devices with low computing power. Our secure computation protocol LPCP becomes of use in such circumstances. LPCP's advantages of fast execution and low communication overhead make it possible for mobile devices to execute MPC protocols. Supposing there are two users \(User_{1}\), \(User_{2}\) with mobile devices who wish to measure the distance between each other in an APP locally. The main idea is as follows. As the local APP service only makes sense in a limited and effective range, we divide the geographical positions into many \(n\times m\) two-dimensional planes, where \(n,m\leq\frac{2^{1}}{\delta}\). Here, the notation \(\lambda\) is the security parameter, and \(\delta\) is the amplification factor. Then, the location of each user is mapped into the coordinate system \((x_{i},y_{i})\) in a co-located rectangle area. Concretely, the location of \(User_{1}\) is scaled up by \(\delta\) and mapped into the integer coordinate system \((x_{1},y_{1})\). The location of \(User_{2}\) is also scaled up by \(\delta\) and mapped into the integer coordinate system \((x_{2},y_{2})\) so that our LPCP can perform arithmetic operations. The problem of the privacy-preserving distance measurement is now transformed into calculating the polynomial \((x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}\), which can be efficiently solved by the LPCP protocol. In the setup phase, both mobile devices obtain their geographical information from the location service and map the geographical information into the integer coordinate system \((x_{1},y_{1})\) and \((x_{2},y_{2})\). The security parameter \(1^{\lambda}\) of LPCP is assumed to be fixed to a static value. To avoid the known-plaintext attack, each mobile device adds a relatively small noise \((e_{i},e_{i}^{\prime})\), where \(e_{i},e_{i}^{\prime}\leq 2^{\lambda/\delta}\) to its location \((x_{i},y_{i})\) to conceal its real position. After the pre-processing, the coordinate of \(User_{1}\) becomes \((x_{1}+e_{1},y_{1}+e_{1}^{\prime})\), and the coordinate of \(User_{2}\) becomes \((x_{2}+e_{2},y_{2}+e_{2}^{\prime})\) where the introduced small noise \(e_{1},e_{1}^{\prime},e_{2},e_{2}^{\prime}\) does not cause a distance result error. In the key generation phase, both mobile devices implement the KeyGen algorithm to generate the prime tuple and the randomness as Section 4. In the encryption phase, \(User_{1}\) plays the role as sender and \(User_{2}\) plays the role as receiver. \(User_{1}\) executes the sender's encryption scheme to encrypt messages \(x_{1}+e_{1}\) and \(y_{1}+e_{1}^{\prime}\), respectively. \(User_{2}\) executes the receiver's encryption scheme to encrypt messages \(x_{2}+e_{2}\) and \(y_{2}+e_{2}^{\prime}\), respectively. \(User_{1}\) and \(User_{2}\) deal with the x-coordinate and y-coordinate calculations separately. The remaining re-encryption phase, evaluation phase, and decryption phase are the same as Section 4. In the re-encryption phase, \(User_{2}\) executes the Re-Enc algorithm. In the evaluation phase, \(User_{1}\) executes the Eval algorithm. In the decryption phase, \(User_{2}\) executes the Dec algorithm.