下载掌阅APP，畅读海量书库
立即打开
安全多方计算问题是从众多具体的密码学问题中抽象出来的，对它的研究以及由此得到的一些结论对于具体的密码学问题具有指导性意义。安全多方计算提供了对任何密码协议问题在原则上的实现方法，它是分布式密码学和分布式计算研究的基础问题，更是分布式密码协议的核心。安全多方计算拓展了传统的分布式计算以及信息安全的范畴，为网络协作计算提供了一种新的计算模式，对保障网络环境下的信息安全具有重要价值。利用安全多方计算协议，一方面可以充分实现网上的互联合作，另一方面又可保证秘密的安全性。
安全多方计算结构如图2-2所示。安全多方计算的主要思路是所有参与者联合起来可以用一种特殊的方法计算含有许多变量的任何函数，其中每个参与者都知道该函数的输出，但不知道关于其他参与者的任何输入。因此，安全多方计算问题可描述为 n 个参与者 P ={ P 1 , P 2 ,…, P n }，每个参与者 P i 持有一个秘密输入 x i ，希望共同计算一个函数 f ( x 1 , x 2 ,…, x n )=( y 1 , y 2 ,…, y n )，计算结束后有如下要求。
图2-2 安全多方计算结构
（1）正确性。任意的 P i ∈ P 都得到正确的输出 y i 。
（2）保密性。 P i 的秘密输入没有泄露给其他参与者 P j ∈ P -i 。
设参与者集合 P ={ P 1 , P 2 } , P 1 和 P 2 要共同安全地计算函数 f ： f 1 × f 2 → f 1 × f 2 ,( x 1 , x 2 )→( y 1 , y 2 )，其中 y 1 = y 2 = x 1 x 2 。参与者 P 1 秘密输入 x 1 , P 2 秘密输入 x 2 。其大致计算流程如下。
第一轮： P 1 发送消息 m 1 给 P 2 ，其中 m 1 混淆了 x 1 和一些随机数 r 1 。
第二轮： P 2 发送消息 m 2 给 P 1 ，其中 m 2 混淆了 x 2 和一些随机数 r 2 。
最后一轮（设为第k轮）: P 1 发送消息 m k 给 P 2 （或 P 2 发送消息 m k 给 P 1 ）。
协议结束后，参与者根据交互过程中得到的信息分别进行计算， P 1 和 P 2 分别得到 y 1 和 y 2 。这里的正确性是指 y 1 = y 2 = x 1 x 2 ，保密性是指对 P i ( i =1,2)得到的信息不会比( x i , y i )以及由此推导的信息更多。
众所周知，安全多方计算最早是由Yao于1982年提出的，即广为人知的百万富翁问题，其实际上是用于解决两个整数比较大小的安全两方计算问题。随后，众多研究者对安全多方计算进行了广泛的研究，产生了一批代表性的成果。目前的研究工作可以分为两类。第一类工作致力于在理论上研究任意函数的一般化的安全多方计算方法，这类研究在理论上具有重要价值，但是目前的研究结果都存在着计算时间长、存储空间小以及通信复杂度高的问题，还不能应用于解决实际问题。另一类工作重点讨论特定函数的多方计算，以期对特定的问题找到更高效的实用解决方案。在安全多方计算领域中，通用型协议的研究关注安全多方计算的一般化结论，对实际应用协议所能达到的安全强度、通信性能等都给出了指导性的结论，这些研究结论是具体应用协议的基础。