Secure two-party line segments intersection scheme and its application in privacy-preserving convex hull intersection

Abstract

The model and framework of secure multi-party computational geometry were presented based on the existing protocols.The new framework has three dimensions,the math model,the security model and the communication model.Using the new model and framework,a secure two-party line segments intersection protocol based on Paillier homomorphic encryption scheme is proposed.This protocol solves the problem that the existing secure two party intersect-determination schemes of line segments cannot output the exact coordinates of the intersection.The security of the protocol is demonstrated using Goldreich method.The results show that this protocol has better efficiency than the existing ones.In addition,the secure two-party line segments intersection in malicious model is also designed.As an application,a privacy-preserving convex hull intersection protocol is proposed based on the O’Rourke scheme.This application makes up for the gap in privacy-preserving convex hull intersection protocol in the area of secure multi-party computational geometry.

Keywords

• cryptography;secure multi-party computational geometry;secure two-party line segments intersection scheme;privacy-preserving;convex hull intersection scheme