安全多方计算：点包含与两多边形相交面积的隐私保护协议

本文主要探讨的是"保护私有信息的两多边形相交面积计算"这一主题，它属于隐私保护计算几何（PrivacyPreserving Computational Geometry，PPCG）领域，这是一个特殊的安全多方计算（Secure Multi-Party Computation，SMC）问题。在半诚实模型的假设下，研究者针对军事和商业场景中的具体需求，设计了一个点包含于多边形的判定协议，该协议是基于点线叉积协议构建的，旨在确保参与者的数据隐私在分布式几何计算中得到保障。 文章的核心内容首先介绍了PPCG问题的基本概念，即参与者在共同解决几何问题时，能够保密各自的输入信息，避免信息泄露。以军事中的轰炸区域判定为例，如果A方要轰炸某地区而不想波及B方的秘密据点，就需要使用点包含于多边形的判定协议来判断。在商业上，两个组织想要在某个地区合作开发市场而不重叠过多区域，涉及的就是两多边形相交面积的计算问题。 文献[4]作为早期工作，奠定了PPCG的基础，解决了点的包含、多边形相交、最近点对以及凸包等问题，并通过点积协议部分解决了相关问题。随后的研究者们对这一领域进行了深入探讨，比如[5]讨论了几何对象的相对位置判定，[6]提供了点与圆、椭圆关系的判定方法，[7]关注点线关系判定及其在相交问题和点包含问题中的应用，[8]利用叉积协议设计了点与凸多边形位置关系的判定，以及[9]提出的点与星形多边形和简单多边形的位置关系判定协议。 本文的重点在于，基于前面的理论和技术基础，设计并分析了一种新的保护私有信息的两多边形相交面积计算协议。这个协议不仅考虑了协议的正确性，即它能准确地计算出两个多边形的相交面积，还着重于其安全性，确保在多边形判定和面积计算过程中，参与者的隐私得到有效保护。此外，作者还评估了新协议的复杂性，即在实际计算效率上的表现，这对于实际应用至关重要。 这篇论文在保护隐私的前提下，拓展了PPCG在计算几何问题中的应用范围，为解决现实世界中的安全多方计算问题提供了一种有效的解决方案，具有较高的实用价值和理论意义。