安全多方计算技术研究与应用

张卷美　徐荣华

摘要：认为同态密码的本质是通过密文运算，实现相对应的明文运算。基于同态密码、格理论密码，分别设计了安全多方计算协议，解决了安全两方线段求解直线相交问题和聚类分析中一种经常遇到的加权平均问题。认为目前安全多方计算的实际应用比较滞后，但随着其理论的不断成熟以及各种密码理论基础技术的不断发展，安全多方计算最终会为新时代下的信息安全提供服务。

关键词：安全多方计算；同态加密；格密码

安全多方计算是密码学的基础问题之一，概括了大多数密码协议，如认证协议、在线支付协议、公平交换协议、拍卖协议、选举协议、密文数据库查询与统计等等。在电子选举、电子投票、秘密共享等场景有关广泛的应用[1-2]。

1 安全多方计算的概念

针对安全多方计算，2004年Goldreich给出了一个简单、完整、统一形式化定义[3]。他将安全多方计算抽象成一个随机过程：[U1、U2、……、Un]是n互不信任的参与方，共同计算函数[f（x1，x2，…，xn）=（y1，y2，…，yn）]，其中函数f是一个计算复杂度为概率多项式的随机函数，Ui拥有秘密输入[xi∈（0，1）*]，通过计算希望获得[yi∈（0，1）*]，但不向其他参与方泄露任何信息。

在理想的世界中，假设第三方是可信的，计算函数f，则其计算时间亦为概率多项式时间，抽象为交互式图灵机，其执行过程为可信第三方收集各方输入，然后计算结果，再分别秘密发送结果给对应参与方。理想世界中敌手IA执行协议过程中获取到的输出变量为IDEAL（IA）。

在现实的世界中，可信第三方不存在，同样计算函数f，则需要收集各方输入，然后计算输出结果，再分别秘密发送结果给对应参与方。理想世界不同的是敌手RA可以窃听并收集诚实参与方之间的通信信息，但不能修改其通信内容。现实世界中敌手IA执行协议过程中获取到的输出变量为REAL（RA）。

对于现实世界中的任意敌手RA，都存在相应理想敌手IS，若在计算过程中，使得IDEAL（IA）和REAL（RA）计算不可区分，即 IDEAL（IA）≈REAL（RA），则认为安全多方计算协议是安全的。

2 同态加密理论在安全多方

计算中的应用

同态加密[4]能够在不对密文解密的情况下，对密文进行计算，从而实现对明文的计算，这与安全多方计算中在不泄露任何数据隐私信息的情况下完成安全计算的需求不谋而合。

目前，同态密码是密码学领域研究的热点之一。同态的分类较为常见的是：单同态、双同态、无限同态和有限同态，这是一个较为概括性的分类方法。

上述安全多方计算协议借助交互多方中的某一位成员进行计算，其他成员只与该成员进行交互，最终计算方将所得结果秘密传送给各个成员。该方案类似于单方交互协议，可以最终实现安全多方计算，但是在效率上有待提高。

4 结束语

作为密码学研究的一个重要方向，安全多方计算既古老又年轻。与理论研究成果相比，安全多方计算的实际应用比较滞后，主要是效率和安全性还不能完全满足现实的需求。根据安全多方计算的特点，我们已经为各种不同的应用场景设计了相应的安全多方计算方案，主要集中在大数据隐私保护、云计算和文数据库检索和统计等安全性需求较高的应用场景中。未来还有很多研究要做，主要集中在恶意型下的多方安全计算问题中，因为恶意模型环境下参与方可以完全不遵守协议规则。虽然在现阶段，安全多方计算的应用还存在困难，但是随着安全多方计算理论的不断成熟以及各种密码理论基础技术的不断应用，安全多方计算最终会走入我们的实际生活，为互联网时代、云计算时代、大数据时代的信息安全服务。

参考文献

[1] YAO Q Z. Protocols for Secure Computations[C]// Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science，Chicago， USA， 1982： 160- 164

[2] GOLDREICH O， MICALI S， WIGDERSON A. How to Play Any Mental Game or A Completeness Theorem for Protocols with Honest Majority [C]//STOC 1987， 1987： 218-229

[3] GOLDREICH O. Foundations of Cryptography： Volume II - Basic Applications [M]. Britain： Cambridge University Press， 2004

[4] GENTRY C. A Fully Homomorphic Encryption Scheme [D]. USA： Stanford University， 2009

[5] DU W L. Secure Multiparty Computation Problems and Their Applications[C]//A Review and Open Problems New Security Paradigms Workshop 2001， Cloudcroft ， New Mexico， USA， 2001

[6] 刘文， 王永滨. 安全多方信息比较相等协议及其应用[J]. 电子学报， 2012， 40（5）： 871-876

[7] 陈志伟，张卷美，李子臣. 基于ElGamal变体同态的安全两方计算协议设计[J]. 通信学报， 2015， 36（2）： 1-8

[8] 刘立强，李子臣.一种基于NTRU的安全两方计算协议[C]//全国信息隐藏暨多媒体信息安全学术大会（CIHW）， 北京， 中国， 2012

[9] 胡予濮. 一个新型的NTRU类数字签名方案[J]. 计算机学报， 2008， 31（9）： 1661-1666