保护私有信息的叉积协议及其应用

叉积是计算几何中关于线段算法的核心.在计算叉积的算法中,若输入的点或线段由不同的用户提供且无须保护这些用户的隐私时,可以假设至少有一个用户能够获得所有的输入信息,从而用传统的方法解决问题.但是,当用户输入数据的隐私需要得到保护时,传统算法或对传统算法做简单改进均不能满足要求,而需要设计新的模式来解决问题.对此提出了半诚实模型下保护私有信息的点线叉积计算协议,讨论和分析了其安全性与正确性,并且以保护私有信息的线段相交判定为例说明了其用途.

隐私保护的点与任意多边形位置关系判定

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

无茫然第三方的安全两方向量优势统计协议

安全两方向量优势统计是一类特殊的安全多方计算问题,用于统计两方在不泄露各自私有向量信息的前提下,满足大于关系的分量数目。但现有的安全两方向量优势统计协议都依赖于茫然第三方,协议的安全性和效率较低。为此,在半诚实模型下,利用同态加密算法和向量叉积协议,提出一个无需茫然第三方支持的两方向量优势统计协议。理论分析结果表明,该协议无需茫然第三方即可提高协议的安全性。该协议的通信轮数为2,通信代价较低。在此基础上,将该协议应用于安全两方向量分量和的排序,也能显著提高排序性能。