科研之友
微信
新浪微博
Facebook
分享链接
摘要
点与多边形位置关系判定的保密计算是一种非常有用的安全多方计算几何应用,目前已有的方案仅支持凸多边形的关系判定.本文提出一种有效隐私保护的点与任意多边形位置关系判定方案.该方案使用模拟射线的判定法将点与任意多边形位置关系的判定问题转化为任意一条过点的射线与多边形相交点数的奇偶性判定问题.设计中首先提出一种精简高效的叉积协议,该协议利用符号位编码将明文空间划分为两个不相交的子空间,分别用于点的正负坐标到明文空间的映射空间从而实现了支持负数的叉积运算,然后基于该叉积协议并利用同态加密方案设计一种隐私保护下的点与多边形位置关系的判定协议,以计算射线与多边形的相交点数,最后利用模拟范例证明该协议的安全性.现有点与多边形位置关系判定方案通常只适用于凸多边形的情况,本文方案不仅能支持对凸多边形的判定且能支持对凹多边形的判定.模拟实验显示本文提出的叉积协议的运行效率相对于已有的叉积协议提高了67.5%.由于避免使用了复杂的密码原语,本文提出的判断方案获得了线性的计算复杂度和通信开销.
- 单位
