# 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
\(B_{1}\) executes \(\Pi\) with \(A_{1}\) by dressing up as \(A_{2}\), that is, \(B_{1}\) selects \(y^{\prime}\) simulation protocol and makes \(F(A_{1}(x),y^{\prime})=F(A_{1}(x),y)\). 1. 2. 1. \(B_{1}\) and \(A_{1}\) execute the protocol and send \(\left\{A_{1}(C_{1b}^{i^{\prime}},C_{2b}^{i^{\prime}})\right\}\) in step 7 to \(A_{1}\). 2. In step 9, \(B_{1}\) verifies the information he asked \(A_{1}\) to publish in step 8. 3. In steps 10-12, \(B_{1}\) selects, calculates, and publishes the information according to \(\Pi\). 4. In step 13, \(B_{1}\) calculates \(m_{b}^{\prime}\) and publishes it. 5. In step 14, the information sequence \(S^{\prime}\) is obtained. In the process of the protocol, there are two situations: 1. \(A_{1}\) receives the message and ignores TTP, so: \[IDEAL_{F,\overline{B}}(x,y)=\left\{A_{1}(C_{1b}^{i^{\prime}},C_{2b}^{i^{ \prime}}),m_{b}^{\prime},S^{\prime},\bot\right\}\] (8)Conversely, that is:

\[IDEAL_{F,\overline{B}}(x,y)=\left\{A_{1}(C_{1b^{\prime}}^{i^{\prime}},C_{2b}^{i^{ \prime}}),m_{b}^{\prime},S^{\prime},F(A_{1}(x),y^{\prime})\right\} \tag{9}\]

In steps 7-14, \(\Pi\) uses the same encryption algorithm, so \((C_{1b^{\prime}}^{i},C_{2b}^{i})\overset{c}{\equiv}(C_{1b^{\prime}}^{i^{ \prime}},C_{2b}^{i^{\prime}})\), \(m_{b}^{\prime}\overset{c}{\equiv}m_{b}\), and \(S^{\prime}\overset{c}{\equiv}S\) ensured by the zero-knowledge proof, then:

\[\left\{IDEAL_{F,\overline{B}}(x,y)\right\}\overset{c}{\equiv}\left\{REAL_{ \Pi,A}^{-}(x,y)\right\} \tag{10}\]

Combining the above two cases it is proved that the output of the strategy to \(\overset{-}{B}=(B_{1},B_{2})\) in the ideal model is indistinguishable from \(REAL_{\Pi,A}(x,y)\) in the actual model, which meets Definition 1. Therefore, Algorithm 2 is secure. \(\square\)

## 6 Performance Analysis

### Overall Performance Comparison

This paper analyzes the performance of Algorithm 2 and protocols in other references [29; 30; 31], as shown in Table 1.

### Computational Complexity

In Fang [29], the protocol adopts the GM encryption system. One-time encryption needs two modular multiplication operations, and one-time decryption needs \(\log N\) modular multiplication operations. [PERSON]'s encryption and decryption need \(2n\) times. [PERSON]'s encryption needs \(2n\) times and the multiplication calculation is \(2n\) times. Therefore, a total of \(10n+2n\log N\) modular multiplication operations are carried out. In Dou [30], its protocol adopts the Paillier encryption algorithm. For the Paillier algorithm, one-time encryption or decryption needs \(\log N\) modular multiplications. [PERSON]'s encryption and decryption times are \(2 mn\) and \(1\) respectively; [PERSON]'s encryption times are \(1\). Therefore, the protocol performs a total of \((2 mn+2)\log N\) modular multiplication operations. The protocol proposed by [PERSON] [31] uses the 2 HCL and symmetric-key primitives, and its computational complexity cannot be expressed by modular multiplication. In reference [31], \(m\) is used to represent the length of the label in the 2 HCL index and \(n\) is denoted as the number of vertices in the graph, and the computational complexity of the protocol is \(O(mn)\). In Algorithm 2 of this paper, the GM encryption system is used in steps 1-6. [PERSON] and [PERSON] perform encryption, decryption, and modular multiplication operations \(4n\), \(2n\), and \(2n\) times respectively. Steps 7-14 transformed the judgment conditions into the socialist Millionaires' problem and carried out \(10m\log N+2\) times of modular multiplication. Therefore, the protocol performs a total of \([20n+(4n+10m)\log N+2]\) modular multiplication operations.