3.2.2　安全多方计算

在现实生活中，存在这样一种情况：多方（Multi-Party）期望共同训练各种各样的模型而不泄露他们自己的隐私信息。为了从技术上解决这个问题，安全多方计算（Secure Multi-Party Computation，SMC）应运而生。针对安全多方计算，我们在本节进行了相关研究进展的综述。

1. 安全多方计算的定义

我们如何在利用各方数据计算函数时不泄露隐私信息呢？理想情况下，我们可以假设参与方有一个可信第三方（Trusted Third-Party，TTP）。参与方只需将他们各自的输入交给可信第三方，由可信第三方代表参与者来计算函数的值，并通知参与各方运算结果，如图3-3a所示。

然而在实际情况下，可信第三方往往是不存在的。我们需要设计一种加密协议，在这种协议中，参与方通过互相交换消息学习函数值，而不需要透露谁做了什么，也不需要依赖可信第三方，如图3-3b所示。由此，我们给出安全多方计算的定义。

定义3.3　在多方计算中，假定有n个参与方：P1，P2，···，Pn，他们分别有各自的隐私数据d1，d2，···，dn。参与方要在隐私数据上计算一个公开函数的值F（d1，d2，···，dn）的同时，在技术上保护他们的数据隐私。

从技术角度上讲，安全多方计算在现实生活中有很多应用场景，比如电子投票、私人竞标和拍卖、签名或解密功能共享以及专用信息检索。根据参与方的数量多少，我们将安全多方计算简单分为安全两方计算（代表方法：姚氏混淆电路）和安全多方计算（代表方法：秘密共享），并在接下来的章节分别介绍。

2. 姚氏混淆电路

图灵奖获得者姚期智于1986年提出的混淆电路（Yao's Garbled Circuit，GC）是安全多方计算中的一项重要技术。这项技术最初是为了解决安全两方问题，即姚氏百万富翁问题。这个问题假设有两个百万富翁——Alice和Bob，他们有兴趣知道他们中的哪一个更富裕而又不愿透露自己的实际财富。换成数学语言来表达就是，现在有两个数字a和b，我们想在不泄露其真实值的情况下比较它们的大小。这个问题的解决需要执行一个比较电路的混淆电路协议，对于初学者可能太过复杂。我们这里从一个简单的与门电路问题展开讲解混淆电路协议，这也很容易推广到整个比较电路。假设Alice和Bob想要弄清楚他们是否应该在一个项目上合作，这对他们来说是一个非常敏感的话题，所以双方都不希望对方了解自己的感受，除非对方赞成合作。这里将Alice的意愿记为a，Bob的意愿记为b。为了简化过程，我们将他们的意愿用二进制数字（即｛0，1｝）表示。我们知道，一个电路的基本组成单位是门（Gate），常见的有与门（AND Gate）、或门（OR Gate）、非门（NOT Gate）和异或门（XOR Gate）。图3-4展示了4种常见的门。

每个门对应一个真值表。在最初的混淆电路中，加密和混淆可以用真值表表示。接下来，我们以与门为例来介绍混淆电路的工作流程。这里让Alice扮演混淆电路生成器（或者称为混淆器，可以生成一个混淆的与门然后发送给Bob），Bob扮演求值器（可以在混淆门上求值）。

现在有4种随机字符串，即对应于a=0的情况，对应于a=1的情况。同样的，对应于b=0的情况，对应于b=1的情况。我们用随机字符串来替换真实的输入/输出，那么一个与门的输入/输出真值表如图3-5所示。然后Alice使用与可能的场景（（a=0，b=0），（a=0，b=1），（a=1，b=0）和（a=1，b=1））对应的每一对字符串来加密与该场景对应的输出。将两个字符串输入通过密钥生成函数H导出一个对称加密密钥（加密/解密的密钥相同），并使用该密钥加密与门。最后的混淆门将会产生4个顺序随机的密文。整个混淆电路流程如图3-5所示。

一旦Bob接收到混淆门，他需要精确地解密这样一个密文：对应有真实值a和b，并被加密。为了完成这个目标，他需要从Alice那里接收到和的值。因为Alice知道a的值，所以他可以发送。因为W是随机独立且同分布的，所以Bob将不会从获得任何有关a的信息。然而，将发送给Bob是比较难的，Alice不能直接将和都发给Bob，因为这样Bob可以解密混淆门中的两个密文，违反了多方计算中的安全性定义。同样的，Bob不能要求任何一个他想要的值，因为他不想让Alice了解到b的值。所以，Alice和Bob可以用不经意传输（Oblivious Transfer，OT）方法，让Bob只知道的同时不把b泄露给Alice。注意，为了使这个方法有效，Bob需要知道什么时候解密成功，什么时候解密失败。否则，他无法知道哪个密文会产生正确的答案。

因为Bob需要尝试求解所有的密文，所以引入了大量的计算。为了解决这个问题，研究者们提出用Point and Permute方法，让Bob可以直接定位到需要解密的密文，从而节省大量的计算。我们接下来将对这个方法进行简单的介绍。因为每个门有两个输入，我们一般称输入为线（Wire），现在每个线w除了字符串W0和W1之外，还有选择位（Select Bit）p0和p1一同输入。对于v∈{0，1}，选择位pv等于v⊕r，这里⊕指的是异或运算，其中r是一个随机选择的位（Random Chosen Bit）。所以，选择位pv与v的两个可能值不同，但同时也不会泄露v的信息。每个线同时输入选择位p和字符串W（这里如果当前线是输入线的话，通过不经意传输，否则就解密）。当对门求值时，Bob使用对应于两个输入线（例如，记pi和pj对应于线wi和wj）的两个选择位来确定门k中的哪个密文需要解密。利用Point and Permute优化方法，Alice常常将置于真值表中的第位置（注意，这时不需要再打乱真值表）。

这种方法使得使用更简单、更有效的加密方案（如一次性加密板，one-time pad）成为可能。因为选择位告诉了Bob要解密哪个密文，不再需要像以前那样区分是使用正确密钥解密还是使用错误密钥解密，这样将求值时的计算负载降低了4倍。关于更多的混淆电路优化方法，例如Free XOR和Row reduction，读者可以参考Sophia Yakoubov在2017年写的综述。

这里的二进制输入例子只是一个安全两方计算的简单示意。实际上，Alice和Bob可能都有多个二进制输入，他们可能想要计算一个更复杂的函数（布尔函数）来完成更复杂的任务。例如，它们可能希望计算输入字符串的汉明距离、他们集合的交集大小或者解决前面提到的百万富翁问题。在这种情况下，Alice将会混淆整个电路（也就是比较电路），而不是混淆单个门。对于那些输出是其他门输入的门，他将不加密输出结果，而是加密与输出结果相对应的字符串W，然后用W推导出密文在其他门的解密密钥。

3. 秘密共享

秘密共享是安全多方计算中常见的方法。在秘密共享技术中，我们可以进行多方计算，这里假设有n方，各方拥有数据xi，他们想在数据{x1，x2，···，xn}中计算函数F的值，但是同时不将他们自己的数据泄露给其他参与者。这个过程分为三步：首先，各方对自己的数据生成n份共享，并分发给其他各方。请注意，共享的数据需要满足这样一个条件：只有访问到至少t份共享，才能恢复原始数据。接下来，各方需要在自己接收到的共享上运行一个本地求值算法来得到本地结果。最后一步就是结合各方使用解码算法后的本地结果来恢复函数值F（x1，x2，···，xn）。在这种情景中使用的秘密共享方案称为（t，n）-门限方案。以下针对t的不同取值情况进行讨论。

• t=1：这种情况是没有意义的。
• t=n：这种情况下，参与方需要收集所有的共享才能恢复原始数据。这种方案虽然数据上比较安全，但是也很脆弱（当某个共享不能访问，原始数据将永远无法被恢复出来）。
• 1<t<n：可以表述成更广泛的解释，即n的任意大小的子集。这种情况下，参与方在保证安全性的同时，不需要n份共享即可恢复数据。

然而，这种任意列举的方法随着子集数量的增加变得愈发不现实。比如我们想要通过50个中的任意20个来恢复秘密，将要设计（≈4.7×1013）个方案。这样的设计方案是低效的。我们接下来分别介绍由Shamir和Blakley提出的经典秘密共享方案。

（1）Shamir秘密共享方案

Shamir秘密共享方案是基于拉格朗日插值定理构造的。

定义3.4　对于某个多项式函数，现有给定的t个点：{（x1，y1），（x2，y2），···，（xt，yt）}，其中xi代表自变量取值，yi代表函数在对应自变量上的取值。那么我们可以构造出这样一个拉格朗日插值多项式：

这样的多项式在最高次幂不超过t-1次的情况下存在且具有唯一性。这里的li（x）=一般称为拉格朗日基本多项式（或者插值基函数）。其特点是在xi上取值为1，在其他点xj（j≠i）上取值为0。

有了这样的定理，我们可以先构造一个t-1次的多项式函数：f（x）=at−1xt−1+at−2xt−2+···+a1x1+s，其中s是需要共享的秘密。我们先随机选取t-1个正整数at−1，at−2，···，a1，完成t-1次多项式f（x）的参数形式设定。接着为这个函数生成n份共享，也就是随机选取n个点，即n个不同正整数xn，xn−1，···，x1，同时计算yi=f（xi）。然后把获得的样本点-函数值对（xi，yi）分别分发给各个参与者。

现在，有任意t个参与者想要恢复秘密s，可以先将自己持有的共享（xi，yi）收集起来，即凑出需要的t个样本点，通过将公式（3.10）中x设为0来完成目标，即：

为了方便读者理解，我们简单举一个例子。假设要共享的秘密s=10，我们同时希望t为4的时候可以恢复秘密。因为常数项为s，我们需要指定t-1（3）个参数。方便起见，这里假设a1=1，a2=0，a3=2，所以我们构造出的多项式函数为：f（x）=2·x3+1·x1+s。现在我们需要采样n个点分发给n个参与方（这里假设x=n，实际情况下可以随机选取）时各方收到的共享，即样本点-函数值对（xi，yi）如下：

假设第1、2、5、7参与方凑在一起想要恢复秘密数据，他们现在利用收到的数据可以构造出如下方程组：

a3·13 + a2·12 + a1·11 + s=13

a3·23 + a2·22 + a1·21 + s=28

a3·53 + a2·52 + a1·51 + s=265

a3·73 + a2·72 + a1·71 + s=703

求解这个方程组就可以获得秘密s和三个参数a1、a2、a3。他们也可以利用已知的样本点-函数值对并通过公式（3.11）来单独求解秘密s。上述的例子只是简化版本，实际上假如有不到t方凑到一起，虽然无法直接恢复秘密，但是也可以将秘密从无限多个自然数限定到有限个自然数中，即这种办法目前还不算安全。从几何上想象的话，这种攻击利用了这样一个事实，即我们知道多项式的顺序，从而了解它在已知点之间可能采取的路径。这减少了未知点的可能值，因为它必须位于光滑曲线上。这个问题可以通过有限域算法来解决：现在有较大素数p>n且p>ai（i=1，···，n），计算的样本点-函数值对（xi，yi=f（xi））可替换为（xi，yi=f（xi） mod p），mod是取模运算。详细的证明可以参考其他相关文献，我们在此不再赘述。

Shamir秘密共享方案可以表述为：我们可以用两个点来确定一条直线，用3个点来定义二次曲线，用4个点来定义三次曲线，以此类推。也就是说，可以用t个点来定义一个t-1次多项式函数曲线。

（2）Blakley秘密共享方案

Blakley秘密共享方案与Shamir秘密共享方案有着相似的想法：同一平面上的两条非平行线相交于一点。空间中三个不平行的平面恰好在一点相交。更一般地说，任何n个不平行的（n-1）维超平面相交于一个特定的点。所以，秘密可以被编码为任何一个交点的坐标，如图3-6所示。

考虑到安全性，如果秘密是用所有的n个坐标编码的，即使它们是随机的，内部人员（拥有一个或多个（n-1）维超平面的人）也会获得关于秘密的信息，因为他知道秘密一定在他的平面上。如果内部人员能够比外部人员获得更多关于秘密的知识，那么系统就不再具有信息理论上的安全性。如果只使用了n个坐标中的一个，那么内部人员不会比外部人员知道得更多（也就是说，对于一个二维系统，秘密必须在x轴上）。每个参与者有足够的信息来定义超平面，然后通过计算平面间的交点，并获取该交点的指定坐标来恢复该秘密。

Blakley方案不如Shamir方案节省空间，即Shamir的分享只需与原来的秘密一样大，Blakley则需要是原来秘密的t倍。如果我们对Blakley方案中的平面做一些额外的限制，那么Blakley方案将退化为Shamir方案。也就是说，Blakley方案是Shamir方案的一个更广泛的版本。

值得一提的是，姚氏混淆电路也可以用秘密共享来描述，在文献中称为姚氏共享，但将姚氏共享与其他秘密共享模式结合起来并不简单，需要一个特殊的转换函数（参考Mohassel等人于2017年发表的SecureML相关文章）。关于更详细和更新的秘密共享的介绍，读者可以参考Beimel等人2011年撰写的综述。

4. 不经意传输

不经意传输（Oblivious Transfer，OT）是另一个安全多方计算的基石。Rabin于1981年提出最早期的不经意传输协议。该协议实现了“二取一”的功能，记作（即1-out-of-2）协议。接着，n取1协议、n取m协议相继被提出。下面给出最广泛的n取m协议的定义。

定义3.5　A有输入信息d1，d2，···，dn，有输入索引{i1，i2，···，im}∈{1，2，···，n}，n取m不经意传输协议就是B总能获得dc1，dc2，···，dcm，但无法获得A的其他值，而且A也不知道B的选择{i1，i2，···，im}。

换句话说，在不经意传输协议中，发送方有一个数据库，接收方想要访问这个数据库的特定条目。但是接收方不希望发送方知道它需要访问哪个条目，同样的，发送方也不希望向接收方泄露整个数据库。在安全多方计算中，不经意传输通常作为混淆电路或秘密共享的补充技术。例如，在混淆电路中求值者（Bob）编码它的数据（注意，随机密钥是由Alice持有的）是通过不经意传输方法完成的。

5. 安全多方计算的应用

安全多方计算广泛应用于安全数据库构建和分布式数据挖掘等任务中。在数据挖掘中，早期的工作主要集中在决策树、K均值（K-means）、支持向量机（SVM）和线性回归等模型。随着深度神经网络的发展，人们更多地关注开发适合深度模型的高效多方计算方法，如Chandran等人于2017年发表的EzPC，Juvekar等人于2018年发表的Gazelle，Liu等人于2017年发表的Oblivious。

（1）基于安全多方计算的深度模型可行性分析

具体地说，我们更关注分布式数据挖掘。有很多场景我们不能在本地训练模型，数据可能是分散在多个个体中，如横向数据分布（每一方拥有一个子集数据样本）或纵向数据分布（每一方拥有特征的一个子集），或者数据和模型位于不同的个体。在这种情况下，安全多方计算是一个非常有前途的技术解决方案，但其仍然具有多个重大的挑战，如效率、可拓展性、表现力等。例如，一个典型的神经网络包括线性矩阵乘法、最大池化、非线性激活函数（ReLU，Softmax等）、批归一化、Dropout等。利用秘密共享技术，如Beaver三元组，可以有效地计算矩阵乘法，但对于非线性运算，还没有统一的解决方案。姚氏混淆电路可以通过定义一个布尔电路来执行非线性运算，但它具有极高的计算和通信开销。秘密共享的简单性和与线性操作的兼容性，使得它成为完成这些非线性操作的另一个选择。

（2）与基于同态加密的深度学习框架的简单比较

同态加密（Homomorphic Encryption，HE）虽然只需要一个单一回合的交互，但不支持有效的非线性。例如，nGraph-HE及其扩展构建在Microsoft SEAL库上，并提供了一个安全评估框架，大大改进了CryptoNet的工作，但它使用多项式（如正方形）来激活函数。

相比同态加密，安全多方计算框架通常使用轻量级加密技术，从而可以提供更快的实现方法。MiniONN和DeepSecure使用优化过的混淆电路，只需很少的通信回合，但它们不支持训练和改变神经网络结构来加速算法执行。其他框架，如ShareMind、SecureML、SecureNN或最新的FALCON更依赖于加性秘密共享（Additive Secret Sharing），并允许安全模型评估和培训。它们使用更简单、更高效的基元，但需要大量的通信回合。比如对于ReLU函数来说，SecureNN需要11个回合，FALCON需要5+log2（l）个回合。ABY、Chameleon和ABY3基于所考虑的哪个操作最有效的想法来混合混淆电路和加法或二进制秘密共享。然而，这两者之间的转换是昂贵的，并且这些方法除了ABY3外，不支持训练这种转换。最后，Gazelle将HE和SMC结合在一起，充分利用了两者的优势，但转换成本也很高。

例如，Ryffel等人提出的AriaNN设计了基于秘密共享的安全比较，并将其应用于对ReLU和MaxPooling的评估。结果，他们成功地训练了一个在多个基准数据集上具有令人满意的准确度的VGG16网络。然而，仍然有许多非线性操作不被当前最先进的框架所支持，如Softmax、Dropout等。这些操作对于神经网络获得良好的性能都是必不可少的。因此，我们希望开发支持神经网络中其他基本非线性操作的有效的秘密共享方法。注意，我们在局域网环境下仍然需要大约60小时以在CIFAR-10数据集上训练一个仅4个Epoch的Alexnet。而用相同的设置在本地训练一个Epoch只需要花费几分钟。非线性操作仍然是瓶颈，例如，比较操作使用的随机键与输入大小成比例，因此批次大小被限制在非常小的范围内，从而减缓了收敛速度。为了进一步提高效率，我们可以开发更好的秘密共享协议，或者利用分布式学习，例如将比较操作分布到多个服务器上，这样我们就可以并行地评估它们。