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

张卷美　徐荣华

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

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

安全多方计算是密码学的基础问题之一，概括了大多数密码协议，如认证协议、在线支付协议、公平交换协议、拍卖协议、选举协议、密文数据库查询与统计等等。在电子选举、电子投票、秘密共享等场景有关广泛的应用[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，则需要收集各方输入，然后计算输出结果，再分别秘密发送结果给对应参与方。