一个保护私有信息的多边形相交判定协议

安全多方计算是信息安全领域的研究热点问题之一.保护私有信息的多边形相交判定是一个特殊的安全多方计算问题,在军事、商业等领域有着重要的应用前景.现有多边形相交判定算法的主要操作是执行点积协议,而目前的点积协议在安全性和计算效率上均难以同时满足该判定算法的要求.本文首先设计了一个常数时间的线段相交判定协议,在此基础上提出了一个保护私有信息的判定多边形相交的概率算法;证明了该算法是一个蒙特卡洛偏真算法,理论分析与实验结果均表明,该方法性能优于现有算法.

A Protocol for Privacy-Preserving Intersect-Determination of Two Polygons

At present,research on secure multi-party computation is of great interest in the field of information security.Privacy-preserving intersect-determination of two polygons is a special secure multi-party computation problem,it can be applied in many fields,such as military field and commerce field.Scalar products protocol plays an important role in the known methods of privacy-preserving intersect-determination of two polygons,however,the current scalar products protocols aren't fit for the determination algorithm on the security and the complexity at the same time.In this paper,a protocol for privacy-preserving intersect-determination of two line segments is developed and a probability algorithm for privacy-preserving intersect-determination of two polygons is presented.Both of the theoretical analysis and the experiment results show that the new algorithms are more efficient than the current algorithm.