安全的多边形相交面积计算

Privately Computing Intersection Area of Two Polygons

保护隐私的计算几何是一类特殊的安全多方计算问题,它是指在一个互不信任的多用户网络中,用户输入各自的几何信息共同完成某项计算任务,但不能泄露各自的输入信息,该问题在商业和军事领域有着重要的应用前景.保护隐私的多边形相交面积精确计算问题是一个很新颖的问题,目前尚未有人解决.本文在Paillier同态加密算法的基础上,基于茫然的第三方提出判断线段相交及交点问题协议,然后结合点包含于多边形判定协议,进一步讨论了两多边形相交面积精确计算问题.最后,给出了以上协议的安全性证明和效率分析,并给出了应用实例.

Privacy preserving computational geometry is a kind of secure multi-party computation problem. In this scenario, some us- ers who do not trust each other want to cooperatively perform computing on their private geometrical data while keeping the privacy of the data. This problem has important application prospect in commerce and military. Privately computing the intersection area of two private polygons is a novel problem that has not been investigated. In this study, based on Paillier＇s homomorphic encryption algo- rithm, using a semi-honest third party, we devise a protocol to privately determine whether two private line-segments intersect. If yes, evaluate the intersection point. Then combining point inclusion protocol, we propose a protocol to privately compute the area of the intersected polygon. We prove that these protocols are secure in the semi-honest model using the simulation paradigm, analyze their performance. Finally, we demonstrate an example of their applications.