安全两方线段求交协议及其在保护隐私凸包交集中的应用

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

研究了现有安全多方计算几何协议,提出了安全多方计算几何的模型和框架,从数学模型、安全模型和通信模型3个维度展开描述。针对现有安全两方线段关系判定协议都忽略求解交点坐标的问题,在半诚实模型下基于Paillier同态加密技术提出了安全两方线段求交协议,使用Goldreich证明法进行了理论安全性分析,并在恶意模型下进行了推广。分析结果表明,该半诚实模型下的算法在效率上优于现有算法。作为安全两方线段求交协议的应用,结合O’Rourke算法提出了保护隐私的凸包求交集协议,弥补了安全计算几何领域仅实现了凸包并集算法的缺陷。

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 homomor- phic encryption scheme is proposed. This protocol solves the problem that the existing secure two party inter-sect-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 exist- ing ones. In addition, the secure two-party line segments intersection in malicious model is also designed. As an applica-tion, 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 computa-tional geometry.