A Practical Solution for Privacy-Preserving Approximate Convex Hulls Problem

Convex Hulls Problem is a special case of Privacy-preserving Geometry problems in the inquiry of Secure Multi-Party Computation (SMC). It can be applied in military, commercial and many other fields. However, because of the definition´s inherent defect, current schemes will inevitably disclose the points on the vertices. In this paper, we proposed the concept of privacy-preserving approximate convex hulls problem and provide a practical protocol which is more secure and efficient than previous convex hulls protocols. We also show that it can be applied to finding the approximate intersection area of two private convex hulls.