几类特殊的安全多方计算问题的研究

论文摘要

安全多方计算（Secure Multi-party Computation）是指拥有秘密输入的n方,希望用各自的秘密输入共同计算一个函数。计算结束后,每一方都能接收到正确的输出,并且每一方只能了解自己的输入和输出,而不了解其他方的输入和输出。安全多方计算实际上是网络用户之间的一种分布式协议,它能够使用户在不泄漏各自输入的前提下完成合作计算的任务。安全多方计算问题最早由A.C.Yao提出,它是电子选举、电子拍卖、门限签名等许多应用得以实现的密码学基础。安全多方计算协议牵涉到众多的底层密码协议,目前提出的方案使用到了秘密共享、公钥和私钥加密、同态加密以及不经意传输等诸多常用的安全协议和算法。由于安全多方计算理论对于网络协议的安全具有重要的指导作用,有很多研究人员投入到这个领域来,并且己经取得了丰硕的成果。目前安全多方计算的研究领域包括保护私有信息科学计算问题,保护私有信息计算几何问题,保密数据挖掘问题,安全多方统计分析问题等。本文创新和研究成果体现如下:1)总结了安全多方计算中百万富翁问题的研究现状和现有研究方案。提出了百万富翁问题的扩展问题——安全多方多数据排序问题,利用El Gamal和RSA同态密码体制给出了两个安全多方多数据排序协议。使用半诚实模型下模拟器的定义,对这两个协议的正确性和安全性进行了理论证明。这些协议为保密电子投标和拍卖、保密在线交易等新型电子交易奠定了基础。2)总结了安全两方比较相等问题（即社会主义百万富翁问题）的研究现状和现有研究方案。提出了滑动窗口的模型,利用此模型和交换加密函数设计了一个安全两方比较相等问题新的解决方案,并利用模拟器的思想对该新方案的安全性进行证明。将社会主义百万富翁问题扩展到多方,提出了安全多方信息比较问题,并给出基于多门限秘密分享的安全多方信息比较协议。3)总结安全多方几何计算问题的研究现状和现有研究方案。提出了三个安全多方几何计算的新问题——保护私有信息的点线关系判定问题、安全两方圆计算问题和保护私有信息的三角不等式判定问题。利用已有的安全多方计算工具对上述问题设计了相应的安全协议,并进行安全性和效率分析。4)总结目前基于安全多方计算的保护隐私数据挖掘问题的研究现状和相关研究方案。以现有的离散背景下的百万富翁协议和安全两方乘积协议为基础,扩展了实数背景下的百万富翁比较协议,构造了半诚实模型下安全两方加乘、安全两方加除、安全两方求对数、安全求两向量分量之和最大值四种工具。利用这些工具设计了一个基于半诚实模型的协议,该协议解决了对于任意划分的数据安全构建决策树的核心问题——在保护用户隐私的情况下,从两方的数据中选取具有最大信息增益的属性。其准确度与数据集中时一样,并且能保护分布在两方中数据的安全。基于安全多方计算理论,证明了协议的安全性,分析了协议的计算复杂性和通信复杂性。将设计的安全多方多数据排序协议与已有的安全多方求和协议相结合,给出了在多数据库中进行保护隐私的序列模式挖掘的新方法,对该方法的安全性进行了简单的分析。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 引言
• 1.1.1 信息安全
• 1.1.2 密码学
• 1.2 安全多方计算简介
• 1.2.1 安全多方计算的定义
• 1.2.2 安全多方计算在密码学中的地位
• 1.2.3 安全多方计算的研究背景和研究现状
• 1.3 研究的内容与成果
• 1.4 组织结构
• 1.5 本章小结
• 第二章 安全多方计算的基本概念与相关工作
• 2.1 安全多方计算的参与者、攻击者和安全需求
• 2.1.1 参与者
• 2.1.2 攻击者
• 2.1.3 通信模型
• 2.1.4 安全多方计算模型
• 2.1.5 安全多方计算的安全需求
• 2.2 安全多方计算的密码学工具
• 2.2.1 秘密分享
• 2.2.2 同态加密体制
• 2.2.3 不经意传输
• 2.2.4 Mix-Match网
• 2.3 安全多方计算的安全性
• 2.3.1 相关定义
• 2.3.2 半诚实两方计算的安全定义
• 2.3.3 恶意模型两方计算的安全定义
• 2.4 安全多方计算的相关工作
• 2.4.1 安全多方科学计算问题的研究
• 2.4.2 安全多方统计分析问题的研究
• 2.4.3 安全多方集合计算问题
• 2.4.4 保护隐私的私有信息检索问题
• 2.5 本章小节
• 第三章 百万富翁问题及其扩展问题的研究
• 3.1 百万富翁问题的研究
• 3.1.1 姚氏百万富翁问题的解决方案
• 3.1.2 使用同态加密体制解决百万富翁问题
• 3.1.3 使用不经意传输协议解决百万富翁问题
• 3.2 社会主义百万富翁问题的研究
• 3.3 排序问题的多方保密协议研究
• 3.4 本人的工作
• 3.4.1 基于滑动窗口和交换加密函数解决社会主义百万富翁问题的新方案
• 3.4.2 安全多方多数据排序问题
• 3.4.3 基于多门限秘密分享方案的安全多方信息比较协议
• 3.5 本章小结
• 第四章 安全多方计算几何问题的研究
• 4.1 安全两方点包含问题和安全两方多边形交集问题
• 4.1.1 安全两方点包含问题
• 4.1.2 安全两方交集问题
• 4.2 安全两方线段相交判定问题
• 4.3 安全点、直线、平面等几何对象之间的相对位置判定问题
• 4.3.1 安全两平面相对位置判定问题
• 4.3.2 安全两直线相对位置判定问题
• 4.3.3 安全直线与平面相对位置判定问题
• 4.4 保护私有信息的判定多边形相交问题
• 4.5 本人的工作
• 4.5.1 保护私有信息的点线关系判定协议及其应用
• 4.5.2 保护私有信息的三角不等式判定协议及其应用
• 4.5.3 安全两方圆计算问题的研究
• 4.6 本章小结
• 第五章 基于安全多方计算的保护隐私的数据挖掘
• 5.1 保护隐私的构造决策树分类发现
• 5.2 保护隐私序列模式挖掘
• 5.3 本人的工作
• 5.3.1 保护任意划分的数据隐私的构造决策树分类发现
• 5.3.2 保护隐私的序列模式挖掘新方法
• 5.4 本章小结
• 第六章 结束语
• 6.1 论文工作总结
• 6.2 未来研究
• 参考文献
• 致谢
• 作者在攻读博士学位期间发表的论文