¹School of Computer & Communication Engineering, University of Science & Technology Beijing, Beijing, China
²National High Performance Computing Center, Hefei, China

---

Abstract—As the basic issues of computational geometry, intersection and union of convex polygons can solve lots of problems, such as economy and military affairs. And privacy-preserving judgment of the intersection and union for convex polygons are most popular issues for information security. Traditional method of making the polygons public does not satisfy the requirements of personal privacy. In this paper, a method to compute intersection and union of convex polygons in secure two-party computation (STC) model has been considered, both proportionate partition and unproportionate partition cases are studied. Scan line algorithm is used to figure out the geometry matter, while secret comparison protocol is used for saving the privacy, a series of protocols for this matter is proposed, which combines computational geometry and secure multi-party computation (SMC) technique to achieve the functionality of cooperation calculation without leaking so much privacy. At last, the security, complexity and applicability analysis of the protocols are also discussed.

Index Terms—STC, secret comparison protocol, privacypreserving geometric computation, polygonal intersection, polygonal union.

[PDF]

Cite: Yifei Yao, Shurong Ning, Miaomiao Tian, Wei Yang, "Privacy-preserving Judgment of the Intersection for Convex Polygons," Journal of Computers vol. 7, no. 9, pp. 2224-2231, 2012.