# 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
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Protocol** & **Fairness** & **Cryptography Tools** &
\begin{tabular}{c} **Resist Malicious** \\ **Attacks** \\ \end{tabular} \\ \hline Fang [29] & unfair & GM & \(\times\) \\ Dou [30] & unfair & Paillier & \(\times\) \\ Liu [31] & unfair & Symmetric & \(\times\) \\  & & cryptography & \(\times\) \\ Algorithm 2 & fair & GM, Paillier & \(\surd\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Protocol’s performance analysis. ### Communication Complexity

In Fang [29], the two parties conducted two rounds of communication. In Dou [30], the two parties conducted three rounds of communication. In Liu [31], the number of communication rounds between the client-side and the server-side are three rounds. In Algorithm 2, four rounds of communication are carried out. Table 2 shows the specific comparison. ### Experimental Simulation

We use Python language to simulate Algorithm 2 and references [29; 30], and the consistency of the universal set's potential and input information is maintained. For the above three protocols, 1000 experiments were performed based on different data lengths, and the average value of 10 execution times was randomly taken. As shown in Figure 3, the computational complexity of reference [29] is slightly lower than that of Algorithm 2. In Dou [30], the proposed protocol is designed based on invoking the MPC protocol that takes the absolute value of the difference between two numbers, which greatly increases the amount of calculation, so its computational complexity is higher than Algorithm 2. Compared with references [29; 30], the protocols have little difference in the number of communication rounds, but only Algorithm 2 proposed in this paper can resist malicious attacks. Although the efficiency of Algorithm 2 is not the highest, its complexity mainly comes from steps such as zero-knowledge proof, and this part of the calculation can be outsourced to improve efficiency. ## 7 Applications

The applications of Manhattan distance permeate many aspects of real life. Moreover, the research on MPC of Manhattan distance also has important practical application value, \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Protocol** & **Computational Complexity** & \
\begin{tabular}{c} **Rounds of** \\ **Communication** \\ \end{tabular} &
\begin{tabular}{c} **Resist** \\ **Malicious Attacks** \\ \end{tabular} \\ \hline Fang [29] & \(10n+2n\log N\) & 2 & No \\ Dou [30] & \((2 nm+2)\log N\) & 3 & No \\ Liu [31] & \(O(nm)\) & 3 & No \\ Algorithm 2 & \(20n+(4n+10m)\log N+2\) & 4 & Yes \\ \hline \hline \end{tabular} Note: the computational complexity of most MPC protocols is relatively high, due to the use of some cryptographic tools, such as the cut-choose method and zero-knowledge proof. These calculations do not reveal private data and can therefore be outsourced to improve the efficiency of the protocol.

\end{table} 
Table 2: Efficiency comparison (based on modular multiplication). Figure 3: Time of executing protocols in Fang [29], Dou [30], and Algorithm 2.

such as privacy computation, computer graphics, data mining, and machine learning. The following are some specific application scenarios. 1. Computing distance is a measurement method. Manhattan distance is often used to measure the length of the path in many scientific studies. For example, in the study of biological cryptography, it is often necessary to judge whether the two biological templates are the same or similar. In data mining and machine learning, we often judge the analogy and similarity of individuals. When consuming products, it will also judge the similarity of consumers. Therefore, the similarity of different individuals can be deduced by calculating the distance value of individual feature vectors, that is, the protocol for MPC of Manhattan distance is the basic module for constructing the secret calculation vector similarity protocol. 2. The Manhattan distance between two points can better protect personal privacy and solve the constrained optimization problem.