安全多方计算中若干计算几何协议的研究

摘要

安全多方计算(简称SMC)是指在一个互不信任的多用户网络中，两个或多个用户能够在不泄漏各自私有输入信息时协作执行某项计算任务。这个问题首先由A.C.Yao于上世纪80年代初提出，目前已经产生了许多研究方向，比如数据挖掘、计算几何、统计分析、电子投票等。本文则主要研究了保护私有信息的计算几何问题。具体就是以下四个方面：
　　 首先，研究了最近点对问题。Mikhail J Atallah和Wenliang Du在2001年提出了该问题，但并没有给出具体的实现方法；到目前为止相关的研究文献较少。本文对该问题进行分析研究，利用同态加密方案提出了空间最近点对协议；在安全性和效率方面都有较好的提高。
　　 其次，研究了集合交集问题。集合交集问题在军事，商业等领域具有重要的应用前景，它的研究对实现新型、安全、公平的数据库信息共享有着重要的意义，目前研究成果也很多。本文介绍了其研究进展以及现有协议的不足，然后提出了保护私有信息的两方、三方集合交集协议，并对该协议的安全性和复杂度进行了分析。
　　 再次，研究了空间几何对象的相对位置计算问题。罗永龙，黄刘生等提出了该问题并给出了协议，后又在其博士毕业论文中给予了详细介绍；他们定性研究了计算几何中的点、线、面相对位置的判定，本文则进一步定量研究了线、面之间的角度及线线之间的距离等问题，并提出了具体的求解方案。
　　 最后，研究了空间几何对象的多方协作计算问题。目前的计算几何大多是两方参与的，本文进一步扩展到多方参与的情况，更具有一般性。本文分析了判定三角形形状、四点是否共面等以及求解三角形面积、四面体体积等问题并设计了相应协议。

目录

文摘

英文文摘

声明

第一章 绪论

第二章 安全多方计算概述

第三章 保护私有信息的最近点对问题

第四章 保护私有信息的集合交集问题

第七章 总结与展望

参考文献

致 谢

攻读学位期间发表的学术论文目录

攻读硕士学位期间参加的科研项目