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