# 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
Preparation:

[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)\). Convert points to vectors:

[PERSON] constructs the vector \(A\) = (1,0,0,0,0,0,0,0,0, 1,1,1,1, 0,0,0,0,0) of point \(P\) according to the coding rules. [PERSON] constructs the vector \(B\) = (1,1,1,0,0,0,0,0, 1,1,1,1,1,1,0,0) of point \(Q\) according to the coding rules. Protocol Start:

1. [PERSON] encrypts vector \(A\) with \(pk(A)\) to get \(E_{pk_{(A)}}(A)=(E(1),\ E(0),\ \cdots,\ E(0),\ E(1),\ E(1),\ \cdots,\ E(0))\), and sends \(E_{pk_{(A)}}(A)\) to [PERSON]. 2. [PERSON] encrypts vector \(B\) with \(pk(A)\) to obtain: \(E_{pk_{(A)}}(B)=(E(1),E(1),\ \cdots,E(0),\ E(1),\ E(1),\cdots,E(0))\), and calculates the ciphertext \(E_{pk_{(A)}}(A\oplus B)=E_{pk_{(A)}}(A)\cdot E_{pk_{(A)}}(B)=\{E(1)\oplus E(1), \ E(0)\oplus E(1),\ldots,E(0)\oplus E(0),\ E(1)\oplus E(1),\)\(\ldots,\ E(0)\oplus E(0)\}\) based on the XOR homomorphism of GM encryption system. [PERSON] randomlydisturbs the sequence of elements in \(E_{pk_{(A)}}(A\oplus B)\) to get \(\hat{R}(E_{pk_{(A)}}(A\oplus B))=\{E(0)\oplus E(1),\,E(1)\oplus E(0),\ldots,E(0) \oplus E(0),\ldots,E(1)\oplus E(1)\}\) and sends it to [PERSON]. 3. [PERSON] decrypts \(\hat{R}(E_{pk_{(A)}}(A\oplus B))\) term by term using \(sk(A)\) to get \(\hat{R}(A\oplus B)=\{1,0,\ldots,1\}\) and calculates: \(x=1+0+\ldots+1\). 4. [PERSON] encrypts vector \(B\) with \(pk(B)\) to get: \(E_{pk_{(B)}}(B)=(E(1),\,E(1),\,\cdots,\,E(0),\,E(1),\,E(1),\,\cdots,\,E(0))\), and sends \(E_{pk_{(B)}}(B)\) to [PERSON]. 5. [PERSON] encrypts vector \(A\) with \(pk(B)\) to obtain: \(E_{pk_{(A)}}(A)=(E(1),\,E(0),\,\cdots,\,E(0),\,E(1),\,E(1),\,\cdots,\,E(0))\), and calculates the ciphertext \(E_{pk_{(B)}}(A\oplus B)=E_{pk_{(B)}}(A)\cdot E_{pk_{(B)}}(B)=\{E(1)\oplus E(1), \,E(0)\oplus E(1),\,\ldots,E(0)\oplus E(0),\,E(1)\oplus E(1),\,\ldots,E(0) \oplus E(0)\}\). [PERSON] randomly disturbs the sequence of elements in \(E_{pk_{(B)}}(A\oplus B)\) to get \(\hat{R}(E_{pk_{(B)}}(A\oplus B))=\{E(1)\oplus E(0),E(0)\oplus E(0),\,\,\ldots,E(1 )\oplus E(1),\ldots,E(0)\oplus E(1)\}\) and then sent it to [PERSON]. 6. [PERSON] decrypts \(\hat{R}(E_{pk_{(B)}}(A\oplus B))\) term by term with \(sk(B)\) to obtain \(\hat{R}(A\oplus B)=\{0,0,\ldots,1\}\) and calculates \(y=0+0+\ldots+1\). 7. In steps 7-12, [PERSON] and [PERSON] follow Algorithm 2, which will not be described in detail. In Algorithm 2, [PERSON] and [PERSON] have the same operations, and the status of both parties is fair. Assume [PERSON] is a malicious participant to explain. [PERSON]'s possible malicious behaviors include: using the wrong \(x\) to calculate \(C_{b}\) in step 11, using the wrong \(\lambda_{a}\) to calculate \(m_{a}\) in step 13, etc. Then [PERSON] cannot prove through the zero-knowledge proof in step 14. [PERSON] knows that [PERSON] is a malicious participant, and Algorithm 2 is terminated. If Algorithm 2 is not finished by step 15 and \(x=y\) is obtained, it can be proved that both parties have implemented the protocol in a semi-honest way, and [PERSON] will get the correct conclusion that \(f_{2}(P,Q)=y=6\) in step 17. ### Security Proof

This paper uses the real/ideal model paradigm method to prove the security. In steps 3 and 6 of Algorithm 2, [PERSON] and [PERSON] get \(x\) and \(y\) respectively. We can take \(x\) and \(y\) as the input data for further execution of Algorithm 2 in the first six steps. Executing the protocol with the false \(x\) and \(y\) is equivalent to providing the false input, which is unavoidable under an ideal protocol, so it is not considered.