三点共线的保密判断问题及应用

Privately Determining Protocol on Three Points Are Collinear and Its Applications

安全多方计算问题由图灵奖得主姚期智于上世纪八十年代首先提出,现在已经成为密码学的一个重要研究方向.保护隐私的计算几何是一类特殊的安全多方计算问题,它是指在一个互不信任的多用户网络中,用户输入各自的几何信息共同完成某项计算任务,但不能泄露各自的输入信息.该问题在商业和军事等领域有着非常重要的应用前景.三点共线的保密判定问题是一个很新颖的问题,目前尚未得到解决.在本文的研究中,我们利用paillier同态加密算法,设计了保护私有信息的三点共线判定问题协议,证明了协议的正确性,并用模拟范例证明了协议的安全性.本文利用三点共线判定问题协议作为基本模块,设计了点与线段关系判定问题协议,证明了该协议的安全性与正确性.我们还给出了以上协议的计算复杂性和通信复杂性分析.在本文的最后部分,结合三点共线判定问题协议和点与线段关系判定问题协议,我们给出了保密计算工业中化学混合物按比例的兑制问题的应用实例.

Secure Multi-party Computation was first proposed by A. C. Yao in 1980s. Now, it is a new and important area of cryptography. Privacy preserving computational geometry is a kind of secure multi-party computation problem. In this scenario, some users who do not trust each other want to cooperatively perform computing on their private geometrical data while keeping the privacy of the data. This problem has important application prospect in commerce and military. There is a new problem that three participants want to know whether their positions are collinear or not without disclosing their specific positions. This problem has not been solved. In this study, we propose a protocol for the problem based on Paillier’s homomorphic encryption scheme. We prove the validity of the protocol, we also prove that the protocol is secure in the semi-honest model using the simulation paradigm. We utilize this scheme to propose a solution to privately determining the relationship of points and line-segments. We prove that these protocols are secure using the simulation paradigm, and analyze their performance. At last, we show an application of these two protocols in chemical industry.