# Securely Computing the Manhattan Distance under the Malicious Model and Its Applications
## 5 The MPC Protocol of Computing Manhattan Distance under the Malicious Model
### Specific Protocol  
The specific protocol is as follows (Algorithm 2):  
``` Input: [PERSON] owns point \(P(x_{1},y_{1})\) and [PERSON] owns point \(Q(x_{2},y_{2})\). Output:\(f_{1}(P,Q)=f_{2}(P,Q)=|x_{1}-x_{2}|+|y_{2}-y_{1}|\). Preparation stage: 1. [PERSON] and [PERSON] respectively generate the public and private keys \(pk_{(A)}/sk_{(A)}\) and \(pk_{(B)}/sk_{(B)}\) of the GM encryption system and send their public keys to each other. [PERSON] generates the public key \((g_{a},N_{a})\) and private key \(\lambda_{a}\) of Paillier encryption system and calculates \(\mu=g_{a}^{\lambda_{a}}\text{mod}N_{a}^{2}\). Similarly, [PERSON] generates \((g_{b},N_{b})\), \(\lambda_{b}\), and calculates \(\
u=g_{b}^{\lambda_{b}}\text{mod}N_{b}^{2}\). [PERSON] and [PERSON] exchange \((g_{a},N_{a},\mu)\) and \((g_{b},N_{b},\
u)\). 2. [PERSON] constructs the vector \(A=(P_{11},\cdots,P_{1n},P_{21},\cdots,P_{2n})\) of point \(P\) according to the coding rules. 3. [PERSON] constructs the vector \(B=(Q_{11},\cdots,Q_{1 nr},Q_{21},\cdots,Q_{2n})\) of point \(Q\) according to the coding rules. Processing steps: 1. [PERSON] encrypts vector \(A\) with \(pk_{(A)}\) to get \(E_{pk_{(A)}}(A)=(E(P_{11}),\ \cdots,\ E(P_{1n}),E(P_{21}),\cdots,\ E(P_{2n}))\), and sends \(E_{pk_{(A)}}(A)\) to [PERSON]. 2. [PERSON] encrypts vector \(B\) with [PERSON]'s GM public key to obtain: \(E_{pk_{(A)}}(B)=(E(Q_{11}),\ \cdots,E(Q_{1n}),\ E(Q_{21}),\ \cdots,\ E(Q_{2n}))\), calculates \(E_{pk_{(A)}}(A)\cdot E_{pk_{(B)}}(B)\), and obtains the ciphertext: \(E_{pk_{(A)}}(A\oplus B)=E_{pk_{(A)}}(A)\cdot E_{pk_{(A)}}(B)\) based on the GM encryption system. The \(\hat{R}(E_{pk_{(A)}}(A\oplus B))\) is obtained by randomly disrupting the sequence of \(E_{pk_{(A)}}(A\oplus B)\) and then sent to [PERSON]. 3. [PERSON] decrypts \(R(E_{pk_{(A)}}(A\oplus B))\) term by term using the GM private key to get \(R(A\oplus B)=(d_{11},\cdots,d_{2n})\) and calculates \(x=d_{11}+\cdots+d_{2n}\). 4. [PERSON] encrypts vector \(B\) with \(pk_{(B)}\) to get: \(E_{pk_{(B)}}(B)=(E(Q_{11}),\ \cdots,\ E(Q_{1n}),E(Q_{21}),\cdots,\ E(Q_{2n}))\), and sends \(E_{pk_{(B)}}\) to [PERSON]. 5. [PERSON] encrypts vector \(A\) with [PERSON]'s GM public key to obtain: \(E_{pk_{(B)}}(A)=(E(P_{11}),\ \cdots,E(P_{1n}),\ E(P_{21}),\ \cdots,\ E(P_{2n}))\), calculates \(E_{pk_{(B)}}(A)\cdot E_{pk_{(B)}}(B)\), and then obtains ciphertext: \(E_{pk_{(B)}}(A\oplus B)=E_{pk_{(B)}}(A)\cdot E_{pk_{(B)}}(B)\). The \(\hat{R}(E_{pk_{(B)}}(A\oplus B))\) is obtained by randomly disrupting the sequence of \(E_{pk_{(B)}}(A\oplus B)\) and then sending it to [PERSON]. 6. [PERSON] decrypts \(R(E_{pk_{(B)}}(A\oplus B))\) term by term with his GM private key to obtain \(\hat{R}(A\oplus B)=(e_{11},\cdots,e_{2n})\) and calculates \(y=e_{11}+\cdots+e_{2n}\). [PERSON] and [PERSON] select \(m\) random numbers \(a_{i},b_{i}(i=1,\cdots,m)\) respectively, calculate \((C_{1a}^{i},C_{2a}^{i})=(g_{a}^{a,x}\text{mod}N_{a}^{2},g_{a}^{a}\text{mod}N_{ a}^{2})\), \((C_{1b}^{i},C_{2b}^{i})=(g_{b}^{h_{y}}\text{mod}N_{a}^{2},g_{b}^{h_{y}}\text{mod}N_{ b}^{2})\), and publish \((C_{1a}^{i},C_{2a}^{i})\) and \((C_{1b}^{i},C_{2b}^{i})\) respectively. Using the cut-choose method, [PERSON] selects \(m/2\) groups \((C_{1b}^{i},C_{2b}^{i})\) from \(m\) groups \((C_{1b}^{i},C_{2b}^{i})\). After [PERSON] publishes \(b_{i}y\), [PERSON] verifies \(g_{b}^{h_{y}}\text{mod}N_{b}^{2}=C_{1b}^{i}\). If the verification passes, she continues to execute the protocol, if, terminates the protocol. [PERSON] selects \(m/2\) groups \((C_{1a}^{i},C_{2a}^{i})\) from \(m\) groups \((C_{1a}^{i},C_{2a}^{i})\). After [PERSON] publishes \(a_{i}x\), [PERSON] verifies \(g_{a}^{a,x}\text{mod}N_{a}^{2}=C_{1a}^{i}\). If the verification passes, he continues to execute the protocol, otherwise terminate the protocol. [PERSON] and [PERSON] randomly select one \((C_{1a}^{i},C_{2a}^{i})\) and \((C_{1b}^{i},C_{2b}^{i})\) from the remaining \(m/2\) groups \((C_{1a}^{i},C_{2a}^{i})\) and \((C_{1b}^{i},C_{2b}^{i})\), and select \(a\in Z_{b}^{*}\) and \(b\in Z_{a}^{*}\).