# 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
[PERSON] calculates \(C_{b}=E_{b}(ab_{j}(x-y))=(C_{2b}^{j})^{ax}(C_{1b}^{j})^{-d}r_{1}^{\lambda_{b}} \text{mod}N_{b}^{2}=g_{b}^{ab(x-y)}r_{1}^{\lambda_{b}}\text{mod}N_{b}^{2}\) and sends it to [PERSON]. [PERSON] calculates \(C_{a}=E_{a}(a_{i}b(x-y))=(C_{1a}^{i})^{b}(C_{2a}^{i})^{-b}r_{2}^{\lambda_{b}} \text{mod}N_{a}^{2}=g_{a}^{ab(x-y)}r_{1}^{\lambda_{b}}\text{mod}N_{a}^{2}\) and sends it to [PERSON]. [PERSON] uses \(\lambda_{a}\) to calculate \(m_{a}=C_{a}^{\lambda_{b}}\text{mod}N_{a}^{2}\), [PERSON] uses \(\lambda_{b}\) to calculate \(m_{b}=C_{b}^{\lambda_{b}}\text{mod}N_{b}^{2}\), and publishes \(m_{a}\) and \(m_{b}\) respectively. Both parties verify the correctness of the calculation with the help of \(m\)-zero-knowledge proof. [PERSON] proves \(\log_{C_{b}}m_{a}=\log_{g_{a}}\mu\) and [PERSON] proves \(\log_{C_{b}}m_{b}=\log_{g_{b}}\
u\). If one of them fails to pass the proof, he or she is the malicious participant. If the certificate is passed, [PERSON] calculates \(L(m_{a})/L(\mu)\) to obtain \(a_{i}b(x-y)\), and then obtains \(a_{i}(x-y)\). When \(a_{i}(x-y)=0\), then \(x=y\).. [PERSON] calculates \(L(m_{b})/L(\
u)\) to obtain \(ab_{j}(x-y)\), and then gets \(b_{j}(x-y)\). When \(b_{j}(x-y)=0\), then \(x=y\). If \(x=y\), then \(f_{1}(P,Q)=f_{2}(P,Q)=x=y\). [PERSON] and [PERSON] get \(f_{1}(P,Q)\) and \(f_{2

### Correctness Analysis

The following is a correctness analysis of Algorithm 2:

1. The main purpose of the first six steps in Algorithm 2 is that [PERSON] and [PERSON] calculate the Manhattan distance respectively. In this process, [PERSON] and [PERSON] decrypt using their own GM private key, so they cannot get each other's information. At the same time, in order to prevent the other party from obtaining its own information, the obtained ciphertext is randomly scrambled in steps 2 and 5 and then sent to the other party. 2. In 7-16 steps, the problem of calculating Manhattan distance has been skillfully transformed into the socialist millionaires' problem. 3. In step 13, [PERSON] must calculate \(m_{a}\) correctly, otherwise, it cannot be proved by the zero-knowledge, that is, cheating is impossible. If \(a_{i}x\) in the remaining \(m/2\) group \((C_{1a}^{i},C_{2a}^{i})\) also satisfies \(a_{i}X<N_{a}/2\) and [PERSON] selects \(b<N_{b}/2\), [PERSON] can calculate \(F(x,y)\) after publishing \(m_{a}\). 4. In this process, if [PERSON] wants to successfully implement the malicious behavior, she can only select a \(a_{i}\) that does not meet the requirements, which is not found in the verification in step 8 and is selected by [PERSON] in step 10, so [PERSON] will not get the correct result. But [PERSON] cannot get \(y\), because \(a_{i}b(x-y)\) is unsolvable (an equation has two unknown numbers). 5. If [PERSON] uses the above method to cheat, the maximum success rate of deception is that in \(m\) group \((C_{1a}^{i},C_{2a}^{i})\), \(m-1\) groups meet the requirements, and only one group does not meet the requirements, that is, the maximum probability is \(1/m\). When the probability of success is the largest (i.e., one group does not meet the requirements), when the probability of success of \(m=10\) deception is \(\frac{C_{1}^{5}}{C_{10}^{5}}\times\frac{1}{5}=\frac{1}{10}\) and five groups do not meet the requirements, the probability of success of deception is reduced to \(\frac{C_{1}^{5}}{C_{10}^{5}}=\frac{1}{252}\). When \(m=50\), these two probabilities are reduced to \(2\times 10^{-2}\) and \(7.9\times 10^{-15}\) respectively. If the group greater than \(1/2\) does not meet the requirements, the probability of successful deception will be reduced to 0 (it will always be found in the verification stage). Similarly, [PERSON]'s probability of successful malicious behavior is the same as [PERSON]'s. Therefore, the protocol is secure. ### Example Description

Suppose [PERSON] holds \(P(5,9)\), [PERSON] holds \(Q(8,12)\), and the full set is \(U=\{5,6,7,8,\)\(9,10,11,12,13,14\}\). The output should be \(f_{1}(P,Q)=f_{2}(P,Q)=|x_{1}-x_{2}|+|y_{2}-y_{1}|=6\).