保护私有信息的点包含协议研究

Research on the privacy-preserving point-in-polygon protocol

对现有保护私有信息的点包含协议进行研究,针对算法复杂度高、协议本身的的局限性等问题,在半诚实模型下,提出一种保护隐私的判断点与凸包位置关系协议。首先,利用OT_1n与矢量的几何性质,将传统的点线位置判断问题扩展,设计一种茫然安全点线位置关系判断协议;然后,将此协议作为基础协议,结合安全二分检索法提出最终解决方案。利用Goldreich证明法对协议进行安全性证明,同时分析协议的正确性与算法复杂度。分析结果表明,协议在效率上优于现有方案,并具有可扩展性。

A privacy-preserving point-in-polygon protocol was proposed under semi-honest model, to deal with the problem of high complexity and limitation of the existing protocols. First, an oblivious point-line protocol was designed by extending the traditional point-line protocol, making the use of 1-out-n oblivious transfer and the geometric properties of the vector. Then, based on this protocol and combined with the secure binary search protocol, the final solution was put forward. The security of the protocol was proved with Goldreich method. Meanwihle, the validity and the complexity of the protocol were also be analyzed. It is shown that this new protocol gets the advantage over the existing one in terms of efficiency and enjoys excellent expandability.