¹ Department of Computer Science, Anhui Normal University, Wuhu, China, 241003
² School of Computer & Information, Hefei University of Technology, Hefei, China, 230009

---

Abstract—The problem of closest pair is a basic problem of computational geometry. This problem was studied while considering the privacy and a protocol was proposed to solve it only considering the level of coordinate axis. The protocol ranked the numbers of two parties firstly. After that each party got the orders of his own numbers. Then the two participants used the protocol of private comparison protocol to get the closet pair according to the relative positions of numbers. We analyzed the correctness, the complexity and compared with previous. This protocol will leak some information, but don’t need the third party. This enhances the security of protocol.

Index Terms—Computational geometry; Secure two-party computation; Closest pair; Private comparison

[PDF]

Cite: Chao Cheng, Yonglong Luo, and Wenjuan Cheng, " Research on the Problem of Privacy-Preserving Closest Pair," Journal of Computers vol. 5, no. 7, pp. 1120-1124, 2010.