Privacy-Preserving Approximate Convex Hulls Protocol
Youwen Zhu, Liusheng Huang, Wei Yang, Dong Li, Lingjun Li, Yonglong Luo, Fan Dong · 2009
Secure Multi-party Computation has been a research focus for more than two decades. The Convex Hulls problem is a special case of Secure Multi-party Computation. However, the precise convex hulls will certainly expose every vertex and even bring about unfairness. As a result, the practical approximate convex hulls are in need. In this paper, we summarize and discuss the Convex Hulls problem, and then we present a new more effective protocol to privately find the approximate convex hulls. Furthermore, we analyze the correctness, security, efficiency and performance of the protocol, and compare the new scheme with other privacy-preserving convex hulls protocols. We show that the privacy-preserving approximate convex hulls protocol is more effective than the previous privacy-preserving convex hulls ones, and the new protocol is practical enough in many aspects. Perfectly keeping privacy preserving and eliminating unfairness are the great advantages of our scheme.