保护私有信息的点线关系判定协议及其应用

Privacy-Preserving Point-Line Relation Determination Protocol and Its Applications

在半诚实模型下,利用加法同态加密体制设计了一个保护私有信息的点线关系判定协议;同时利用该协议设计了保护私有信息的线段相交判定问题和保护私有信息的点包含判定问题的解决方案.保护私有信息的点线关系判定协议,可以保密地判断点在直线正侧、负侧和在直线上;保护私有信息的线段相交判定协议,可以保密地判断不同参与方拥有的直线是否相交;保护私有信息的点包含判定协议,可以保密判断不同参与方拥有点和多边形之间的包含关系.最后分析和证明了这些协议的正确性、安全性和复杂性.

A privacy-preserving point-line relation determination protocol based on additive homomorphism encryption is developed in semi-honest model. The privacy-preserving point-line relation determination protocol can be used to solve many privacy-preserving computational geometry problems, such as segments intersection problem and point inclusion problem. The privacy-preserving point-line relation determination protocol can be also used to determine either the point is at the positive side, negative side, or on the line privately. Further more, the privacy-preserving segments intersection protocol can be used to determine two lines supplied by different users intersect securely; and the privacy-preserving point inclusion protocol can be used to determine the relation of a point and a polygon supplied by different users. Finally, the correctness, security and efficiency of these protocols are analyzed.