Quantum k-means algorithm based on Manhattan distance

He Zhang, Huanzhang Ling

Hiroshi Ohno

Xin Liu, Xiaomeng Liu, Ruiling Zhang +3 more

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.

Wen Liu, Wei Zhang

Secure Manhattan distance computation allows two parties to privately compute the Manhattan distance of their points, which is important and has broad applications. In this paper, we present a protocol for secure Manhattan distance computation based on phase shift operation. Because of quantum mechanics' physical principle, our protocol can also resist outside attacks and don't leak any private information of participants.

Min Hou, Shibin Zhang, Jinyue Xia

Jing Li, Song Lin, Kai Yu +1 more