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

Privacy-Preserving Cross Product Protocol and Its Applications

作　　者：罗永龙[1,2] 黄刘生[1,2] 荆巍巍[1,2] 徐维江[1,2] 陈国良[1,2] 

机构地区：[1]中国科学技术大学计算机科学技术系,合肥230027 [2]安徽省计算与通讯软件重点实验室,合肥230027

出　　处：《计算机学报》2007年第2期248-254,共7页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2006CB303006);国家自然基金(60573171);安徽省高校省级自然科学研究重点项目基金(2006KJ024A);中国博士后科学基金(20060390700);教育部博士点基金(20060358014);安徽省自然科学基金资助~~

摘　　要：叉积是计算几何中关于线段算法的核心.在计算叉积的算法中,若输入的点或线段由不同的用户提供且无须保护这些用户的隐私时,可以假设至少有一个用户能够获得所有的输入信息,从而用传统的方法解决问题.但是,当用户输入数据的隐私需要得到保护时,传统算法或对传统算法做简单改进均不能满足要求,而需要设计新的模式来解决问题.对此提出了半诚实模型下保护私有信息的点线叉积计算协议,讨论和分析了其安全性与正确性,并且以保护私有信息的线段相交判定为例说明了其用途.In computational geometry, computing cross products is at the heart of line-segment methods. If the points and the line segments of the cross product algorithms are of several users and the privacy of any user is not considered, the problem can be solved through traditional methods, because we can assume the existence of a user who knows inputs from all the users. Howev- er, the traditional methods or simply improved methods aren＇t fit for the situation where no user is willing to disclose his private data to other users and some new methods should be developed to solve the new problem. In this paper, privacy-preserving pointegment cross product protocol is firstly presented under the semi honest model and its security and correctness are also discussed. Privacy-preserving cross product protocol can be used to solve many privacy-preserving computational geometry problems. As an example, a secure protocol for determining whether two line- segments intersect is developed based on the privacy-preserving point-segment cross product protocol.

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

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