# Securely Computing the Manhattan Distance under the Malicious Model and Its Applications
###### Abstract  
Manhattan distance is mainly used to calculate the total absolute wheelbase of two points in the standard coordinate system. The secure computation of Manhattan distance is a new geometric problem of secure multi-party computation. At present, the existing research secure computing protocols for Manhattan distance cannot resist the attack of malicious participants. In the real scene, the existence of malicious participants makes it necessary to study a solution that can resist malicious attacks. This paper first analyzes malicious attacks of the semi-honest model protocol of computing Manhattan distance and then designs an advanced protocol under the malicious model by using the Goldwasser-Micali encryption system and Paillier encryption algorithm, and utilizing some cryptographic tools such as the cut-choose method and zero-knowledge proof. Finally, the real/ideal model paradigm method is used to prove the security of the malicious model protocol. Compared with existing protocols, the experimental simulation shows that the proposed protocol can resist malicious participant attacks while maintaining high efficiency. It has practical value.  
secure multi-party computation; Manhattan distance; malicious model; cut-choose method; real/ideal model paradigm +
Footnote †: journal: Applied  
is often necessary to compute a similarity measure across different samples when making a classification, which requires computing the \"distance\" across samples, and it is a practical method for distance calculation. In early computer graphics, screens were constructed from pixel dots whose coordinates were generally integers and it was costly to carry out float operations, but using Manhattan distance, which requires only addition and subtraction, can greatly improve the operation speed. Therefore, the study of Manhattan distance has extremely important theoretical value and practical significance.  
At present, there is some research on the secure computing of Manhattan distance [29; 30; 31], and the existing protocols are designed in the semi-honest model. Consequently, it is particularly significant to study the MPC protocol of Manhattan distance to resist malicious attacks. In this paper, an MPC protocol for calculating the Manhattan distance is designed. The contributions are as follows:  
1. Firstly, the protocol in Reference [29] is analyzed and found that some situations may be attacked by malicious participants.
2. According to the possible attacks of malicious participants, we design a new MPC protocol for computing the Manhattan distance can resist malicious attacks. In the process of designing the protocol, we use the Goldwasser-Micali and Paillier encryption algorithm, the cut-choose and zero-knowledge proof methods are used. The secure computation of the Manhattan distance will be converted into the Millionaires' problem to further improve the efficiency of the protocol.
3. The real/ideal model paradigm method is used to prove the security of the proposed malicious model MPC protocol. The performance and efficiency of the protocol are analyzed and simulated by experiments compared with existing protocols.