Privacy-preserving computational geometry

Privacy-preserving computational geometry is the research area on the intersection of the domains of secure multi-party computation (SMC) and computational geometry. Classical problems of computational geometry reconsidered from the point of view of SMC include shape intersection, private point inclusion problem, range searching, convex hull,^[1] and more.^[2]

A pioneering work in this area was a 2001 paper by Atallah and Du,^[3] in which the secure point in polygon inclusion and polygonal intersection problems were considered.

Other problems are computation of the distance between two private points^[4] and secure two-party point-circle inclusion problem.^[5]

Problem statements

The problems use the conventional "Alice and Bob" terminology. In all problems the required solution is a protocol of information exchange during which no additional information is revealed beyond what may be inferred from the answer to the required question.

• Point-in-polygon: Alice has a point a, and Bob has a polygon B. They need to determine whether a is inside B.^[3]
• Polygon pair intersection: Alice has a polygon A, and Bob has a polygon B. They need to determine whether A intersects B.^[3]