安全多方计算几协议的研究与应用.pdf

摘要 摘 要 不断发展的网络技术以及高性能计算机、网格技术的出现，极大地改变了传 统意义上的合作计算方式。处于不同地理位置的多个用户可以利用性能优良的网 络协同完成某个任务，但这也带来一个亟待解决的问题，敏感数据的安全性如何 保证。安全多方计算(Secure Multi-Party Computation,SMC)正是在这样的背景之 下产生。它是指在一个互不信任的多用户网络中，两个或多个用户能够在不泄漏 各自私有输入信息时协同执行某项计算任务。我们在研究上将任务抽象成某个具 体的函数，安全多方计算要求满足两个基本性能，一是要保证正确性，二是要达 到必威体育官网网址性。这个问题首先由图灵奖得主A.C.Yao 于上世纪80 年代初提出，目前 已经产生了许多研究方向，比如数据挖掘，计算几何，统计分析，电子选举等。 本文的研究工作主要集中在保护私有信息的计算几何问题上。计算几何作为 计算机科学的一个分支，它主要研究解决几何问题的算法。计算几何在现代工程 和数学领域有着广泛应用，比如在图像处理、机器人技术、超大规模集成电路设 计和统计等诸多领域有着十分重要的应用。在安全多方计算领域中的计算几何有 着全新的应用前景。目前已经有很多学者对涉及到保护私有信息的计算几何问题 进行了研究，并得到了很好的结果。本文的主要工作有： 首先，研究了最近点对问题。在2001 年Mikhail J Atallah 和Wenliang Du 前 瞻性的提出该问题的时候，并没有给出具体的实现方法，并且直到目前为止相关 的研究文献很少。本文重点对该问题进行分析研究，利用点积协议和距离计算协 议设计了一个保护私有信息的最近点对协议。并且与已有的协议进行了比较，该 协议在安全性方面有很大的提高。 其次，深入研究了保护私有信息的点包含问题。分析总结了现有协议的实 现原理以及优缺点，包括利用三角形面积协议，利用随机化方法以及利用叉积协 议判定。在此基础上针对基于叉积协议的点包含问题做了局部的修改，使之达到 更大的安全性；文章接下来，设计了一个保护私有信息的射线与线段相交协议， 并且利用该协议提出了基于交点个数的判定点是否包含在凹多边形内部的协议。 该协议可以大大的扩大点包含问题的应用范围。 紧接着，研究了圆包含问题以及多边形的包含问题。提出了解决这两个问题 -I- 安全多方计算几何协议的研究与应用 的相关协议并且分析了其安全性，正确性及效率问题。类似的SMC 领域的包含 问题可以作为在军事，商业等领域的计算模型，同时也有助于SMC 技术在计算 几何领域的进一步应用。 最后，研究了几何计算中的保护私有信息的多边形凹凸性的判定问题。首先 基于线性变换构建了两类叉积协议，然后结合向量优先协议设计出保护私有信息 的多边形凹凸性的判定协议，讨论和分析了其安全性和正确性。该协议在军事领 域或者必威体育官网网址的图像处理领域有着广泛的应用背景。 关键词： 安全多方计算，计算几何，点包含，最近点对，凸包，协议 -II- Abstract Abstract Along with the continuous development of network technology, and with the appearance of high quality computer and net rid, the traditional ways of cooperation are greatly changed.Two or more parties not in the same places want to jointly complete a specific task by the network technology. But it also brought a problem to be solved as soon as