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

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

作　　者：罗永龙[1] 黄刘生[1] 徐维江[1] 荆巍巍[1] 

机构地区：[1]中国科学技术大学计算机科学技术系

出　　处：《电子学报》2007年第4期685-691,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60573171);教育部博士点基金(No.20060358014);中国博士后科学基金(No.20060390700);安徽省高校自然科学研究重点项目(No.2006KJ024A;No.2007KJ043A);安徽省自然科学基金(No.070412043)

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

关 键 词：安全多方计算 计算几何 点积协议 算法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]