若干离散问题的安全多方计算协议研究

作     者：廖干才 

作者单位：北京邮电大学 

学位级别：硕士

导师姓名：罗守山

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：密码学 安全多方计算 同态加密体制 点积协议 私有信息检索 

摘      要：安全多方计算(Secure Multiparty Computation)是指拥有秘密输入的n方,希望用各自的秘密输入共同计算一个函数。计算结束后,每一方都能接收到正确的输出,并且每一方只能了解自己的输入和输出,而不了解其他方的输入和输出。安全多方计算实际上是网络用户之间的一种分布式协议,它能够使用户在不泄漏各自输入的前提下完成合作计算的任务。 近年来,特殊的安全多方计算已经成为国际密码学界的研究热点,并且成为电子选举、在线协作服务以及电子拍卖等诸多应用得以实施的密码学基础。几乎所有分布式环境下的协议都可以看成是一类特殊的安全多方计算协议。安全多方计算协议常使用同态加密体制、秘密共享以及不经意传输等安全协议和算法。 在安全多方计算的领域,设计安全的、高效的、实用的特殊安全多方计算协议,如安全两方点积协议、安全多方交集协议、私有信息检索协议等都是非常有意义的工作。 本文在综合论述安全多方计算的基础上,详细地介绍了作者在安全多方计算的应用领域的协议设计方面的工作。首先,本文将对安全多方计算的理论基础进行详细介绍。对于目前前人在安全多方数学计算,如私有信息检索、矩阵计算、计算几何、统计分析、数据挖掘等方面的相关成果进行全面的整理。其次,本文将作者在研究生阶段所得到的研究成果分章节进行了阐述和扩充。 1.提出了一个高效的安全两方点积协议,分析了该协议的正确性和安全性,对比了同类协议的效率。 2.基于安全点积协议,提出了一个向量属于空间协议,并分析了协议的安全性和效率。 3.分别设计了安全多方交集协议和安全多方集合排序协议。并对协议自身的安全性和效率进行了分析。 4.研究了安全多方计算中的几何计算问题,总结了其发展和研究成果;提出了一个解决安全多方判断三角不等式地协议,并将该协议应用于安全多方几何计算方面。 5.研究了私有信息检索问题,运用秘密共享技术,提出了一种高效率的对称私有信息检索协议;并将单项对称私有信息检索协议推广到一次能够查询多条记录的多项对称私有信息检索协议;并分析了安全性和效率。另外提出了一种保密计算数据库第K值问题的改进方案。