张明武, 张依梦, 谌 刚

1. 湖北工业大学 计算机学院, 武汉430068

2. 密码科学技术国家重点实验室, 北京100878

3. 桂林电子科技大学 计算机与信息安全学院, 桂林541004

1 引言

几何位置关系的判定在实际中应用非常广泛. 在军事系统中, 两雷达在不同范围半径进行位置探测,二者需要知道彼此探测区域的关系以判定是否彼此探测覆盖; 另外, 在社交网络中, 基于地理位置信息进行好友推荐, 并判断用户间的位置关系是社交网络的重要因素[1]. 随着大数据和人工智能等技术的发展,用户彼此间交互的信息量急速增加, 这可能造成用户信息的泄露[2,3]. 因此, 在参与多方有效判定各种位置关系的同时保护各自信息不被泄露是个不可忽视的问题[4].

安全多方计算(Secure Multi-party Computation, SMC)[5]为隐私保护的位置判定问题提供了有效的解决思路, 也为大多数学者的研究提供了一个重要方法. 安全统计分析[6,7]、安全几何计算[8,9]以及安全科学计算[10]等是常见的安全多方计算问题, 而隐私保护的几何位置关系判定问题, 是安全几何计算问题的核心问题之一. 针对该问题, 提出了具体的点与圆(多边形)[8,11–14]、点与直线[15,16]、及点与平面间[9,17]等位置判定的解决方案. Li 等人[14]提出隐私保护的点与凸(凹) 多边形位置关系判定协议, 首先提出的安全两方三角形面积计算协议, 然后通过判定三角形面积的符号位来解决凸多边形中的点包含问题. 基于文献[14] 中利用三角形面积判定的思想, Chen 等人[8]提出了点与凸多边形位置……