A Protocol of Privacy-Preserving Closest Pair in Two Dimensional Space

The problem of closest pair is a basic problem of computational geometry. This paper investigates the problem of privacy-preserving closet pair and designs a protocol. This protocol bases on Euclid-distance measure protocol and private comparison protocol. The main idea of this protocol is using the Euclid-distance measure protocol to respectively compute the distances of one party´s one point and the other party´s two points. Then the private comparison protocol is called for comparing the two distances. This paper analyzes the security and complexity. The protocol doesn´t need the third party and can be easily extended to multi-dimensional space.