安全多方计算理论研究的理论综述

1 引言
　　安全多方计算（Secure Mutiparty Computation，SMC）是解决在一个互不信任的多用户网络中，两个或多个用户能够在不泄漏各自私有输入信息时，协同合作执行某项计算任务的问题。它在密码学中拥有相当重要的地位，是电子选举、门限签名以及电子拍卖等诸多应用得以实施的密码学基础。
　　本文首先介绍安全多方计算理论的相关概念和数学模型，分析它与密码学的关系，进一步指出它的应用领域，然后综述其基本协议和近年来的研究成果，从存在的问题入手探讨其研究热点。
　　2 基本概念和数学模型
　　考虑这样一个问题，一组参与者，他们之间互不信任，但是他们希望计算一个约定函数时都能得到正确的结果，同时每个参与者的输入是保密的，这就是安全多方计算问题。
　　如果有可信第三方（Trusted Third Party，TTP），参与者只需将自己的输入保密传输给TTP，由TTP计算这个约定函数后，将结果广播给每个参与者，上述问题得以解决。但是事实上，很难让所有参与者都信任TTP。因此，安全多方计算的研究主要是针对无TTP情况下，如何安全计算一个约定函数的问题。
　　通俗地说，安全多方计算是指在一个分布式网络中，多个用户各自持有一个秘密输入，他们希望共同完成对某个函数的计算，而要求每个用户除计算结果外均不能够得到其他用户的任何输入信息。
　　可以将安全多方计算简单地概括成如下数学模型：在一个分布式网络中，有n个互不信任的参与者P1，P2，...Pn，每个参与者Pi秘密输入xi，他们需要共同执行函数
　　F：（x1，x2，...，xn）→（y1，y2，...，yn）
　　其中yi为Pi得到的相应输出。在函数F的计算过程中，要求任意参与者Pi除yi外，均不能够得到其他参与者Pj（j≠i）的任何输入信息。
　　由于在大多数情况下y1=y2=...=yn，因此，我们可以将函数简单表示为F：（x1，x2，...，xn）→y。
　　3 安全多方计算理论的特点
　　安全多方计算理论主要研究参与者的隐私信息保护问题，它与传统的密码学有着紧密的联系，但又不等同。同时，也不同于传统的分布式计算，有其独有的特点。
　　3.1 安全多方计算是许多密码协议的基础
　　从广义上讲，多方参与的密码协议是安全多方计算的一个特例。这些密码协议可以看成是一组参与者之间存在着各种各样的信任关系（最弱的信任关系就是互不信任），他们通过交互或者非交互操作来完成某一任务（计算约定函数）。这些密码协议的不同之处在于协议的计算函数不一样，如电子拍卖是计算出所有参与者输入的最大值或最小值，而门限签名是计算出一个正确签名。
　　3.2 安全多方计算不同于传统的密码学
　　密码学研究的是在不安全的媒体上提供安全通信的问题。一般来说，一个加密系统由某一信道上通信的双方组成，此信道可能被攻击者（窃听者）窃听，通信双方希望交换信息，并且信息尽可能不被窃听者知道。因此，加密机制就是将信息进行变换，在信息传送过程中防止信息的篡改和泄漏，目的是系统内部阻止系统外部的攻击。
　　而安全多方计算研究的是系统内部各参与方在协作计算时如何对各自的隐私数据进行保护，也就是说安全多方计算考虑的是系统内部各参与方之间的安全性问题。
　　3.3 安全多方计算也不同于传统的分布式计算
　　分布式计算在计算过程中必须有一个领导者（Leader）来协调各用户的计算进程，当系统崩溃时首要的工作也是选举Leader；而在安全多方计算中各参与方的地位是平等的，不存在任何有特权的参与方或第三方。
　　因此，安全多方计算拓展了传统的分布式计算以及信息安全的范畴，为网络计算提供了一种新的计算模式，也为数据保护建立了一种安全策略，并开辟了信息安全新的应用领域。
　　4 安全多方计算理论的应用领域
　　目前的应用主要在电子选举、门限签名、电子拍卖、联合数据查询和私有信息安全查询等方面。
　4.1 电子选举
　　电子选举协议是安全多方计算的典型应用，也得到研究者们的广泛重视。将一个安全多方计算协议具体应用到电子选举工作中，设计出的电子选举协议可满足几个功能：计票的完整性、投票过程的鲁棒性、选票内容的保密性、不可复用性和可证实性。
　　4.2 门限签名
　　门限签名是最为熟知的一个安全多方计算的例子，研究门限签名的文献很多，目前也比较成熟。应用安全多方计算理论的门限签名能够很好地解决这个问题，门限签名有两个好处：一是主密钥不是放在一个地方，而是在一群服务器中分享，即使其中某些服务器被攻破，也不会泄露主密钥；二是即使某些服务器受到攻击，不能履行签名的任务，其他的服务器还可以继续保持CA的功能，完成签名任务。这样CA的安全性可以得到大大提高。
　　4.3 电子拍卖
　　安全多方计算理论的提出，使得网上拍卖成为现实，电子拍卖是电子商务中非常活跃的一个方面，已经提出的电子拍卖方案很多，大部分方案都是采用可验证秘密共享协议（Verifiable Secret Sharing，VSS）或使用其思想。电子拍卖协议应该具有一些性质：协议的灵活性、保密性、鲁棒性、可验证性。
　　4.4 联合数据查询
　　信息技术的发展，促进了多学科的交叉协同，资源共享成为新技术研究的必要手段。但是各个数据库经营者都要求自己的私有信息或知识版权等，避免资源共享时泄露自身保密数据。安全多方计算理论可以解决上述问题，即在不同数据库资源共享时，多个数据库可以看成多个用户联合起来进行数据查询。
　　4.5 私有信息安全查询
　　在数据库查询中，如果能够保证用户方仅得到查询结果，但不了解数据库其它记录的信息；同时，拥有数据库的一方，也不知道用户方要查询哪一条记录，这样的查询过程被称为安全查询。
　　5 安全多方计算理论的基础协议
　　5.1 茫然传输协议
　　茫然传输协议（Oblivious Transfer Protocol，OTP）是SMC的一个极其重要的基础协议，从理论上说，一般模型下的安全多方计算问题均可以通过茫然传输协议来求解。
　　茫然传输（Oblivious Transfer，OT）的概念是等人于1981年首次提出来的。它是指发送方Alice仅有一个秘密输入m，他希望以50%的概率让接收方Bob获得m，然而Bob不希望Alice 知道他是否得到秘密m。随后，产生了很多OT的变种，如等人于1985年提出二选一茫然传输、r等人于1987年推广为多选一茫然传输。
　　5.2 秘密比较协议
　　秘密数据比较是安全多方计算的一个基本操作，它是指计算双方各输入一个数值，他们希望在不向对方泄露自己数据的前提下比较出这两个数的大小，当这两个数不相等时，双方都不能够知道对方数据的任何信息。该问题在设计高效的安全多方计算协议中起着关键作用。
　　目前有两类秘密判定协议：第一类秘密判定协议是判定两个数据是否相等，若不相等则双方均无法知道对方的任何数据信息；另一类秘密比较协议能判定出两个输人的大小关系。
　　5.3 置换协议
　　安全多方置换问题可以描述为：Alice有一个私密向量X=（x1，x2，...，xn），Bob有一个私密置换函数？仔和私密向量R=（r1，r2，...，rn），Alice需要获得？仔（X+R），同时要求Alice不能获得？仔和任何ri的信息，Bob也不能获得任何xi的信息。
　　5.4 点积协议
　　点积问题可以描述为：Alice有一个私密向量X=（x1，x2，...，xn），Bob有另一个私密向量Y=（y1，y2，...，yn），Alice需要获得u=X·Y+v=■xiyi+v，这里v仅是Bob知道的随机数。同时要求Alice不能获得X·Y的值和任何yi的信息，Bob也不能获得u的值和任何xi的信息。
　　6 安全多方计算理论研究进展
　　安全多方计算理论自提出起，由于它拓展了计算和信息安全范畴，其研究者众多、发展迅速，并取得了较大的成绩，研究进展经历了理论形成、协议设计完善和应用研究等阶段。
　　6.1 理论形成
　　安全多方计算问题首先由于1982年提出。5年后，ich、S.M icali和son三位学者提出了密码学安全的可以计算任意函数的安全多方计算协议。他们证明了在被动攻击情况下，n-private协议是存在的，在主动攻击情况下，n-resilient协议是存在的，并展示了如何构造这些协议。
　　1988年，-Or、sse和son，以及、u和d几乎同时证明了在信息论安全模型中，被动攻击情况下当串通攻击者数t　　6.2 安全多方计算协议的设计完善
　　随后，安全多方计算吸引了大量学者的注意，他们根据不同的计算模型与安全模型对安全多方计算协议做了一些有益的改进，主要体现在几个方面，这也是研究者们关注的焦点：①设计一般意义的安全多方计算协议；②对安全多方计算协议进行形式化的定义；③对通用的安全多方计算协议进行裁减将其应用于不同的实际问题；④构造新的安全多方计算协议；⑤对安全多方计算攻击者的结构进行定义。
　　6.3 应用研究
　　1998年，Gold Reich指出用通用协议来解决安全多方计算问题中的一些特殊实例是不切实际的，对于一些特殊问题需要用一些特殊方法才能达到高效性。这一思想迅速促进了安全多方计算在一些特殊领域应用研究的发展，近年来很多学者已将安全多方计算技术引入传统的数据挖掘、计算几何、私有信息检索、统计分析等领域。
　由此产生了新的研究方向，如保护隐私的数据挖掘（Privacy Preserving Data Mining，PPDM）、保护隐私的计算几何（Privacy Preserving Computation Geometry，PPCG）、私有信息检索（Private Information Retrieval，PIR）、保护隐私的统计分析（Privacy Preserving Statiscal Analysis，PPSA）等，为解决一些重要的安全应用问题提供了技术基础。
　　7 安全多方计算理论研究热点
　　目前学者们针对安全多方计算理论的研究，主要在密码学和信息论两种安全模型下进行，研究热点集中在几个方面。
　　7.1 一般安全多方计算协议
　　为节省资源，研究一种通用一般化的协议，目的在于设计一种高效、安全、能够计算任意函数的安全多方计算协议，通过这种通用协议来解决所有涉及到的安全多方计算问题。
　　7.2 对一般安全多方计算协议裁减
　　如果一个协议是普适的，那么必然会牺牲一些性能上的代价来满足其广泛适用性。针对一个具体的应用，如电子选举，对一般化的安全多方计算协议进行一点裁减，去掉一些对这个具体应用没有意义的部分，可以大大地提高效率。具体地说，是如何将安全多方计算理论与技术应用到具体的环境。
　　7.3 安全多方计算的定义
　　由于安全多方计算协议的构造形式多种多样，而各研究者基于的安全模型不一致，而得出的应用条件也是不一样的。如i等人针对安全信道模型下的安全多方计算给出了形式化的定义，首先提出可信第三方TTP的安全多方计算，然后考虑如何用协议来模拟TTP的作用。这与其他模型下的安全多方计算的思路和协议构建方法完全不同，即使在同一模型下，但协议的构造方法也会影响到具体应用。
　　虽然安全多方计算的目的、性质、应用环境都得到本领域学者的认可，但是至今还没有一个大家认同的、完备的定义。因此，安全多方计算的完备定义一直是研究热点。
　　7.4 新的安全多方计算协议构造方法
　　目前大部分研究者们在设计安全多方计算协议时，基本都以VSS的子协议为构造基石，设计出的协议在答题结构上都是类似的，这样在解决通信效率和安全性上没有实质性突破。是否存在新的构造方法来设计高效安全多方计算协议，这是研究者们一直在探索的问题之一。
　　7.5 安全多方计算协议生成器
　　现有的许多安全多方计算协议的研究，基本在于安全域定义上如何完成基本运算就停止了。因为，从理论上讲，任何函数可以安全地被计算就已解决私有信息保护问题。但是，距离实际应用还有一步需要跨越。
　　安全多方计算协议计算器目的在于联系基本定义和函数安全计算，其作用就是弥补这具体应用一步，多方计算生成器的输入就是任意函数f和计算域上基本运算的子协议，输出是安全计算函数f的协议。目前，许多学者已经提到了安全多方计算生成器的重要性，但并没有深入研究。
　　7.6 恶意模型下的安全多方计算
　　现在对安全多方计算问题的研究主要基于密码学和信息论等安全模型，要求所有参与方必须严格按照协议的流程进行计算，不能恶意修改协议 的运行或提供虚假数据。
　　而在实际的协作计算中，可能协议的参与方是恶意用户，此时，我们需要设计高效的恶意模型下的安全多方计算协议。尽管从理论上说，任何通用模型下的SMC协议都可以转换成恶意模型下的SMC协议，但这种理论转换在效率上是不可行的。因此，恶意模型下的安全多方计算问题需要得到进一步的研究。
　　8 结束语
　　安全多方计算理论及其应用是一个迅速崛起的、理论性很强的研究领域，它牵涉到密码学的各个分支，有着广阔的应用领域。从理论上讲在分布式的环境中，有多个参与者的任何协议都可以看作是安全多方计算的一个特例。如果我们设计了一个安全高效的安全多方计算协议，那么理论上所有的分布式环境中的多个参与者的协议，都可以用这个安全多方计算协议来解决。所以，从这个意义上来看，安全多方计算协议有着非常诱人的应用前景。
　　参考文献
　　[1] 秦静，张振峰，冯登国 等. 无信息泄漏的比较协议. 软件学报，2004，15（3）：421-427.
　　[2] 罗永龙. 安全多方计算若干关键问题及其应用研究. 中国科学技术大学博士学位论文，2005.
　　[3] 刘木兰，张志芳. 密钥共享体制和安全多方计算. 北京：电子工业出版社，2008.
　　[4] Atallah M J，Du W. Secure Multi-Party Computational Geometry. In Lecture Notes in Computer Science， 2125，Springer Verlag. Proceedings of 7th International Work shop on Algorithms and Data Structures（WADS 2001），Providence， RhodeIsland ，USA. 2001：165-179.
　　[5] Alfred J M， Paul C V， Scott A V.著，胡磊，王鹏等译 . 应用密码学手册. 北京：电子工业出版社，2005：107-223.
　　[6] Li S D， Dai Y Q. Secure Two-Party Computational Geometry. Journal of Computer Science and Technology， 2005，20（2）：258-263.
　　[7] Ronald Cramer， Ivan Damgfird， Ueli Maurer. General secure multi-party computation from any linear secret-sharing scheme. Lecture Notes in Computer Science， 2000（1807）：316-325.
　　作者简介：
　　王婷（1981-），女，北京师范大学，本科学士学位，首都医科大学附属北京妇产医院信息科，助理工程师；主要研究方向和关注领域：网络信息安全。 本文选自《信息安全与技术》2014年第5期，版权归原作者和期刊所有。