# 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
Therefore, only steps 7-17 need to be proven secure. Theorem 1.1: _Algorithm 2 (mentioned as \(\Pi\)) is secure._

Proof of Theorem. : The Algorithm \(\Pi\) is feasible only if at least one of the two parties in the protocol is not a malicious participant, that is, there are two cases that need to be proven secure. (Case I) \(A_{1}\) is honest, \(A_{2}\) is dishonest. In this situation, \(A_{1}\) and \(A_{2}\) execute \(\Pi\), then:

\[REAL_{\Pi,A}(x,y)=\left\{F(x,A_{2}(y),A_{2}(C_{1a}^{i},C_{2a}^{i}),m_{a},S\right\} \tag{3}\]

where \(S\) is the sequence message received by \(A_{2}\) through the zero-knowledge proof. \(A_{1}\) will execute the protocol honestly, and \(B_{1}\) is determined. \(B_{2}\) of the ideal model is indistinguishable from \(A_{2}\) of the actual protocol needs to be proven. The output of \(\stackrel{{-}}{{B}}=(B_{1},B_{2})\) is indistinguishable from \(REAL_{\Pi,A}\) in the actual model (note: \(A_{2}\) is the actual executor of \(\Pi\). Therefore, when proving, the security of \(\Pi\) needs to be verified according to \(A_{2}\)'s behavior, that is \(A_{2}(y)\)). 1. \(A_{1}\) in the actual protocol is honest, so \(B_{1}\) will send right \(x\) to TTP. According to dishonest \(A_{2}\)'s strategy, \(B_{2}\) decides what information to send to TTP. Consequently, the input of \(B_{2}\) is \(A_{2}(y)\). 2. TTP obtains the \((x,A_{2}(y))\) and calculates \(F(x,A_{2}(y))\). 3. \(B_{2}\) dresses up as \(A_{1}\) and executes \(\Pi\) with \(A_{2}\), that is, \(B_{2}\) selects \(x^{\prime}\) and makes \(F(x^{\prime},A_{2}(y))\) \(=F(x,A_{2}(y))\). 1. \(B_{2}\) and \(A_{2}\) execute \(\Pi\) and send the information \(\left\{A_{2}(C_{1a}^{i^{\prime}},C_{2a}^{i^{\prime}})\right\}\) to \(A_{2}\) in step 7 based on Algorithm 2. 2. 2. In step 8, \(B_{2}\) verifies the information he asked \(A_{2}\) to publish. 3. In step 9, \(B_{2}\) publishes the information required by \(A_{2}\). 4. In steps 10-12, \(B_{2}\) selects, calculates, and publishes the information according to \(\Pi\). 5. In step 13, \(m_{a}^{\prime}\) is calculated and published. 6. In step 14, the information sequence \(S^{\prime}\) is obtained. In the process of \(\Pi\), the following can be got: \[IDEAL_{F,\overline{B}}(x,y)=\left\{F(x,A_{2}(y)),A_{2}(C_{1a}^{i^{\prime}},C_{2 a}^{i^{\prime}}),m_{a}^{\prime},S^{\prime}\right\}\] (4) In steps 7-14, \(\Pi\) adopts the same encryption algorithm, \((C_{1a}^{i},C_{2a}^{i})\stackrel{{ c}}{{\equiv}}(C_{1a}^{i^{ \prime}},C_{2a}^{i^{\prime}})\), \(m_{a}^{\prime}\stackrel{{ c}}{{\equiv}}m_{a}\), and the zero-knowledge proof ensures \(S^{\prime}\stackrel{{ c}}{{\equiv}}S\), so: \[\left\{IDEAL_{F,\overline{B}}(x,y)\right\}\stackrel{{ c}}{{ \equiv}}\left\{REAL_{\Pi,\overline{A}}(x,y)\right\}\] (5) (Case II) \(A_{1}\) is dishonest, \(A_{2}\) is honest. There are two cases: 1. [PERSON] gets the result and ignores TTP, then \(\bot\) is sent to [PERSON] by TTP, so: \[REAL_{\Pi,\overline{A}}(x,y)=\left\{A_{1}(C_{1b}^{i}C_{2b}^{i}),m_{b},S,\bot\right\}\] (6) 2. Conversely, \(f_{2}(x,y)\) is sent to [PERSON] by TTP, then: \[REAL_{\Pi,\overline{A}}(x,y)=\left\{A_{1}(C_{1b}^{i}C_{2b}^{i}),m_{b},S,F(A_{1 }(x),y)\right\}\] (7) where \(S\) is the sequence message received by \(A_{1}\). \(A_{2}\) is honest, \(B_{2}\) is determined. \(B_{1}\) of the ideal model is indistinguishable from \(A_{1}\) of the actual protocol needs to be proven. That is, the output of strategy pair \(\overline{B}=(B_{1},B_{2})\) is indistinguishable from \(REAL_{\Pi,\overline{A}}(x,y)\) needs to be proven (note: \(A_{1}\) is the actual executor of \(\Pi\). Therefore, when proving, the security of \(\Pi\) needs to be verified according to \(A_{1}\)'s behavior, that is \(A_{1}(x)\)). 1. According to dishonest \(A_{1}\)'s strategy, \(B_{1}\) decides what information to send to TTP. Therefore, the input value \(B_{1}\) sends to TTP is \(A_{1}(x)\). 2. \((A_{1}(x),y)\) is obtained by TTP to calculate \(F(A_{1}(x),y)\). 3.