第 1 章 引言
安全多方计算
安全多方计算(secure Multi-Party Computation, MPC)研究的是这样一个计算任务：这个任务中有多个参与方，他们各自拥有一些隐私数据，并且想要计算一个关于这些隐私数据的函数。每个参与方都希望得到最终的结果，同时又希望自己的隐私数据不被其他参与方知道。
一个直接的方案是：寻找所有参与方都信任的第三方 \(T\)，将隐私数据发送给 \(T\)，\(T\) 执行所需的计算，然后公布结果，并诚实地删除计算过程中的所有隐私数据。然而，这个方案有两个明显的不足。首先，所有参与方都必须完全信任 \(T\) 能够确保正确性和隐私性。其次，即使 \(T\) 的确是诚实的，这个方案还是创造了一个危险的单点故障：一旦第三方 \(T\) 被攻破，所有的隐私数据都会被泄露。
那么，有没有可能在不依赖单一可信第三方的情况下完成这个任务呢？乍一看，这似乎不太可能，因为最终的结果取决于所有参与方提供的隐私数据。不过，正如本书后续内容所示，无论是在理论上还是实际应用中，都存在可行的解决方案。（注：本节参考了书 [CDN, 2015]，Chapter 1. Reproduced with permission of the Licensor through PLSclear.）
问题描述
让我们把这个任务描述得更精确一些。设参与方的数量为 \(n\)，将参与方记为 \(P_1, …, P_n\)，每个参与方 \(P_i\) 拥有隐私输入 \(x_i\). 所有参与方对要计算的函数 \(f\) 具有共识，即，他们都希望计算 \(y = f(x_1, …, x_n)\). 参与方希望计算过程满足以下两个性质：
正确性：计算输出的结果 \(y\) 是正确的。
隐私性：除了计算结果 \(y\)，没有其他信息被泄露。
满足正确性和隐私性的计算被称为安全多方计算。这里，我们先假设所有参与方都希望获得同样的公共输出；另一种更通用的情况是每个参与方可以获得不同的私有输出。为了简单起见，我们先考虑“单一公共输出”的情况。
第一价格密封拍卖(first-price sealed-bid auction)就是一个典型的实际案例。在这种拍卖方式中，所有竞拍者提交密封的出价，出价最高者以他提交的价格获得拍卖品。在这个场景下，隐私输入 \(x_i\) 就是竞拍者 \(P_i\) 提交的出价（假设 \(x_i\) 各不相同），定义函数 \(f(x_1, …, x_n) = (z, j)\)，其中 \(x_j = z\) 且 \(x_j > x_i, 1 \leq i \leq n, i \neq j\). 也就是说，函数 \(f\) 输出最高价以及出价人的身份，但是不泄漏其他竞拍者的出价。
接下来，我们将用一个简单的协议作为示例，展示如何在不依赖单一可信第三方的情况下安全地计算任何函数。我们先考虑一种比较简单的情况：所有参与方都遵循协议。之后，我们会讨论参与方违背协议时的处理方案。我们假设所有参与方之间可以安全地互相通信，即，\(P_i\) 可以向 \(P_j\) 发送消息 \(m\)，使得没有任何其他参与方可以看到 \(m\)，且 \(P_j\) 知道 \(m\) 来自于 \(P_i\).（注：在实际应用中，这通常可以通过公钥基础设施(Public Key Infrastructure, PKI)来实现。）
安全加法与投票
设有 \(n\) 个参与方 \(P_1, …, P_n\) 想要对某个决议进行投票表决。为此，他们定义计票函数 \(f(x_1, …, x_n) = \sum_{i=1}^n x_i\)，其中 \(x_i \in \{0, 1\}\)，\(x_i = 0\) 表示“反对”，\(x_i = 1\) 表示“赞成”。如果可以安全地计算函数 \(f\)，那么他们就可以得知赞成票的数量，且没有其他信息被泄露（特别是不能泄漏特定参与方的具体投票情况）。下面，我们将设计一个协议来实现安全投票。为了与下一小节保持一致，我们考虑 \(n=3\) 的情况。读者可以自行思考如何对任意的 \(n\) 设计安全投票协议。
秘密分享(secret sharing)。实现这一目标的核心工具是秘密分享。这个词看上去似乎是有点自相矛盾：如果一个东西是秘密，那怎么可以与别人分享呢？秘密分享的关键在于，它允许秘密的持有者（例如 \(P_1\)）向所有参与方“分享”某个秘密 \(x\)，使得当所有参与方聚集在一起时可以恢复出 \(x\)，但是除 \(P_1\) 以外的任何单一参与方都不能独自获得关于 \(x\) 的任何信息。
我们使用的秘密分享方案如下。首先，选择一个素数 \(p\)，定义 \(\mathbb{Z}_p = \{ 0, 1, …, p-1 \}\). 秘密 \(x\) 是 \(\mathbb{Z}_p\) 中的一个数。为了分享秘密 \(x\)，秘密持有者（假设为 \(P_1\)）在 \(\mathbb{Z}_p\) 中均匀随机地选择 \(r_1, r_2\)，并计算 \(r_3 = x - r_1 - r_2 \bmod p\). 换句话说，\(P_1\) 在 \(\mathbb{Z}_p\) 中均匀随机地选择 \(r_1, r_2, r_3\)， 满足 \(r_1 + r_2 + r_3 = x \bmod p\). 然后，\(P_1\) 将 \(r_1, r_3\) 秘密地发送给 \(P_2\)，将 \(r_1, r_2\) 秘密地发送给 \(P_3\)，\(P_1\) 自己保留 \(r_2, r_3\). 这里的 \(r_j, j = 1, 2, 3\) 被称为秘密 \(x\) 的份额(share)。
让我们看看这个方案是否满足秘密分享的基本属性。首先，当 \(P_1, P_2, P_3\) 聚集在一起时，他们可以通过计算 \(x = r_1 + r_2 + r_3 \bmod p\) 来恢复出 \(x\)（正确性）。另外，对于 \(P_1\) 以外的任何单一参与方，例如 \(P_2\)，他知道 \(r_1\) 和 \(r_3\)，但是不知道 \(r_2\)，因此他无法计算出 \(x\)（隐私性）。对于 \(P_3\) 而言，他也一样无法计算出 \(x\).
我们可以用一种更严谨的方式来论证隐私性。从 \(P_2\) 的视角来看，如果任取 \(x_0 \in \mathbb{Z}_p\)，存在 \(x = x_0\) 的可能吗？答案是肯定的。如果 \(x = x_0\)，那么 \(r_2 = x_0 - r_1 - r_3 \bmod p\). 由于 \(r_2\) 是从 \(\mathbb{Z}_p\) 中均匀随机选择的，它所有的取值概率都是均等的。因此，对于任意的 \(x_0 \neq x_1\)，\(x = x_0\) 的概率与 \(x = x_1\) 的概率都是相等的。由此我们得出结论，\(P_2\) 的秘密份额没有泄漏关于 \(x\) 的任何信息。从 \(P_3\) 的视角来看，也完全同理。
注意，这里的隐私性是信息论意义上的。即使 \(P_2\) 拥有无限的计算能力，他也无法获得关于 \(x\) 的任何信息。 在这个秘密分享方案中，每个参与方持有秘密的两个份额，我们称之为复制秘密分享(replicated secret sharing)。 现在，我们基于它构造安全加法协议。
安全加法协议。 安全加法协议中，\(P_1\)，\(P_2\) 和 \(P_3\) 使用上述方式对他们的输入 \(x_1\)，\(x_2\) 和 \(x_3\) 秘密分享。不难发现，参与方在本地将秘密份额相加并公布结果，即可计算 \(x_1\)，\(x_2\) 和 \(x_3\) 的加和。协议如图 1.1所示。
然后，我们需要论证隐私性，也就是除了计算结果 \(y\) 之外，没有其他信息被泄露。以 \(P_1\) 为例，我们刚才已经论证过，这里使用的秘密分享方案不会泄露 \(x_2, x_3\) 的任何信息。\(P_1\) 自己可以计算出 \(s_2\) 和 \(s_3\)，因此 \(P_1\) 在协议中唯一看到的新信息就是 \(s_1\). 那么 \(s_1\) 会不会泄漏 \(x_2, x_3\) 的信息呢？这是不会的。因为协议的输出 \(y = s_1 + s_2 + s_3 \bmod p\)，这是 \(P_1\) 本应该从协议中得到的信息。而如果 \(P_1\) 知道了 \(y\)，他就可以反推出 \(s_1 = y - s_2 - s_3 \bmod p\). 所以 \(s_1\) 是可以根据协议的输出 \(y\) 计算出来的，因此 \(s_1\) 不可能泄露 \(y\) 以外的任何信息。对于 \(P_2\) 和 \(P_3\) 而言，也完全同理。
这种证明方式被称为基于模拟的证明。我们希望论证：给定参与方应该知道的信息，可以高效地计算（模拟）出他在协议中看到的所有信息。如果可以实现这样的模拟，那么说明：除了参与方应该得到的输出，协议没有泄漏任何额外信息。这种证明方式将在本书后面的章节中多次出现。
注意，\(P_1\) 的确可以计算出一些信息：他可以计算 \(y - x_1 = x_2 + x_3\)，即另外两人的投票总和。读者可能会感到困惑，认为这是协议的漏洞。然而，基于最终结果 \(y\) 和他自己的输入 \(x_1\)，\(P_1\) 一定可以计算其他人的投票总和——即使参与方借助可信第三方来计算 \(y\)，\(P_1\) 也仍然可以得到 \(y - x_1\) 这一信息。这是无论协议如何设计都无法阻止的！因此，这不是协议的漏洞，协议能达到的最好效果就是让参与方只知道自己的输入和最终结果。
安全乘法与配对
不难发现，基于上述秘密分享方案，式（式 1.1）中的每一项都可以由某个参与方在本地计算出来。例如，\(P_1\) 拥有 \(a_2, b_2, a_3, b_3\)，那么他可以计算 \(a_2 b_2, a_2 b_3, a_3 b_3, a_3 b_2\). 然后，参与方使用安全加法协议将这些项相加，就可以实现安全乘法了。协议如图 1.2所示。
让我们验证一下安全乘法协议的正确性和隐私性。首先，由式（式 1.1）可知这样计算出的 \(y\) 是正确的。其次，协议中除了本地计算之外，只调用了安全加法协议。我们在前面论证过，安全加法协议没有泄漏除了 \(y\) 以外的任何信息，因此，安全乘法协议也没有泄漏额外信息，满足隐私性。
安全乘法的一个实际应用是实现用户的配对。例如，在某个恋爱交友网站上，Alice和Bob希望了解对方对自己是否感兴趣，但又不想面对被对方拒绝的风险。我们可以让Alice选择 \(a \in \{0, 1\}\)，其中 \(a = 1\) 表示“感兴趣”，\(a = 0\) 表示“不感兴趣”；Bob也以同样的方式选择 \(b\). 然后，他们可以让恋爱交友网站作为 \(P_3\)，三方执行安全乘法协议，输出 \(y = ab\). 显然，只有当Alice和Bob都选择“感兴趣”时，输出结果才会为1. 并且如果Alice选择了 \(a = 0\)，那么她将不会知道Bob的输入，也就避免了Bob可能被拒绝的尴尬场面。
注意，这里的恋爱交友网站 \(P_3\) 虽然协助了协议的完成，但是他并不是单一可信第三方。具体而言，\(P_3\) 只能知道Alice和Bob的配对是否成功，而不能知道其他任何信息。特别是，当配对不成功时，\(P_3\) 无法得知是Alice对Bob不感兴趣，还是Bob对Alice不感兴趣，或是双方都选了不感兴趣。
一个自然的问题是：如果没有 \(P_3\) 的协助，Alice和Bob能否两个人自己实现安全的乘法和配对呢？答案是肯定的。但是在这种场景下，协议无法做到信息论意义上的安全，必须假设某些问题在计算上是困难的。在本书后面的章节，我们将介绍这样的协议。
如果参与方不遵守指令？
在上面所讲的协议中，我们假设参与方总是遵循协议规定执行。然而，现实情况往往并没有那么美好——参与方可能不遵守指令，目的是获得更多的信息，或者让协议输出错误的结果。我们将不遵守指令的行为分为两类：首先，参与方可以将自己的输入替换为另一个；其次，在协议执行过程中，参与方可以违背协议的规定。
输入替换。 以刚才的恋爱交友网站配对为例。如果Alice想了解Bob的输入，那么她可以始终选择 \(a = 1\)（表示“感兴趣”）。 此时，只有当Bob也选择 \(b = 1\) 时，输出才会为1；如果输出为0，说明Bob选择了 \(b = 0\). 这样，Alice就可以破坏Bob的隐私性。
稍加思考就会发现，我们不可能通过协议的设计来解决这个问题。无论协议如何设计，恶意的参与方总是可以随心所欲地替换自己的输入，然后用这个新的输入执行协议。对于安全多方计算来说，这是它与生俱来的特性。
回到刚才的配对场景，如果Bob担心Alice会通过始终选择 \(a = 1\) 来破坏Bob的隐私性，那么他唯一的办法就是退出！如果他选择参与，那么他必须假设其他参与方会合理地选择自己的输入。这个假设成立的原因可能是：如果Alice实际上对Bob不感兴趣，那么选择 \(a = 1\) 将可能导致配对成功，这对Alice来说是时间的浪费！此类关于个体行为动机的研究属于“博弈论”的范畴，不在本书的讨论范围之内了。
违背协议。 前面讲过，无论协议如何设计，参与方总是可以替换自己的输入，这是我们无法阻止的行为。而另一种情况是，在协议执行过程中，参与方可能会违背协议的规定，为了使协议输出错误的结果或者得到更多的信息。例如，在一次拍卖中，参与方可能试图用低价成为拍卖的赢家。我们当然不希望这样的情况发生。但与前一种情况（输入替换）相比，这是可以通过协议设计来解决的。
让我们再研究一下安全加法协议。安全加法协议的第一步，是参与方将自己的输入秘密分享。以 \(P_1\) 为例，协议要求他均匀随机选取 \(r_{1,1}, r_{1,2}, r_{1,3}\)，使得 \(x_1 = r_{1,1} + r_{1,2} + r_{1,3} \bmod p\)，然后发送 \(r_{1,1}, r_{1,3}\) 给 \(P_2\)，发送 \(r_{1,1}, r_{1,2}\) 给 \(P_3\). 此时，\(P_1\) 可以违背协议的规定，将 \(r_{1,1}, r_{1,3}\) 发送给 \(P_2\)，并将 \(r'_{1,1}, r_{1,2}\) 发送给 \(P_3\)，其中 \(r'_{1,1} \neq r_{1,1}\). 此时，\(P_1\) 的输入 \(x_1\) 没有被良好定义，因而协议会输出什么结果、泄漏哪些信息，都是未知的。
幸运的是，有一个简单的方法可以检测到这种行为：当 \(P_2\) 和 \(P_3\) 从 \(P_1\) 那里接收到他们的秘密份额时，\(P_2\) 将它的 \(r_{1,1}\) 值发送给 \(P_3\)，\(P_3\) 将它自己的 \(r_{1,1}\) 值发送给 \(P_2\). 然后他们检查这个值是否相同。类似地，\(P_1\) 和 \(P_3\) 可以检查 \(P_2\) 发送的份额是否一致，\(P_1\) 和 \(P_2\) 可以检查 \(P_3\) 发送的份额是否一致。通过这一步检查，我们可以保证每个参与方的输入都被良好定义了。
在秘密分享阶段之后，各方在本地将秘密份额相加并公布。我们仍以 \(P_1\) 为例，协议要求他计算 \(s_2\) 和 \(s_3\) 并公布。\(P_1\) 可能通过公布 \(s'_2 \neq s_2\) 来违背协议，这有可能导致协议输出错误的结果 \(y = s_1 + s'_2 + s_3 \bmod p\). 然而，\(P_3\) 也需要计算 \(s_1\) 和 \(s_2\) 并将其公布。因此，\(P_1\) 和 \(P_3\) 都应该公布 \(s_2\) 的值，参与方可以通过观察 \(P_1\) 和 \(P_3\) 是否公开了相同的 \(s_2\)，来检查是否存在这种违背协议的行为。同样地，参与方检查两个版本的 \(s_1\) 和两个版本的 \(s_3\) 是否相同来避免违背协议的行为。
在秘密分享阶段和输出阶段增加了一致性检查后，新的安全加法协议满足如下特性：当任何单一参与方违背协议时，另外两个参与方始终能够检测到这一点。这种特性被称为恶意安全性：任何除了“输入替换”以外的违背协议的行为都将被检测到。我们将在后面的章节中详细讨论它的形式化定义以及实现恶意安全性的各种方法。
通用解决方案
现在，我们已经设计了在 \(\mathbb{Z}_p\) 域中进行一次安全加法或乘法的协议。那么，如果我们希望对输入进行多次计算呢？不难发现，在安全加法协议的最后一步，如果参与方不公布 \(s_\ell, \ell = 1, 2, 3\)，那么 \(P_1\) 持有 \(s_2, s_3\)，\(P_2\) 持有 \(s_1, s_3\)，\(P_3\) 持有 \(s_1, s_2\). 这恰恰构成了计算结果 \(y\) 的秘密分享！对于安全乘法协议，因为它的最后一步调用了安全加法协议，所以各参与方也持有结果 \(y\) 的秘密份额。也就是说，如果希望对输入进行多次计算（例如，先做加法再做乘法），只需使用上一步的计算的秘密份额，调用安全加法/乘法协议中的步骤，即可安全地计算下一步。
众所周知，在 \(\mathbb{Z}_p\) 域中的加法和乘法可以模拟任何计算（注：任何计算都可以转化为布尔电路的形式，模素数加法和乘法可以模拟与门、或门、非门。）。因此，我们已经得到了一个可以安全计算任何函数的协议！
让我们庆祝一下我们的初步进展吧！尽管这是在很强的假设下实现的：我们假设参与方会遵循协议的规定（安全乘法协议不能检测违背协议的行为）；我们只考虑了三个参与方的情况；我们假设不会有两个参与方串通；我们假设参与方可以安全地通信，等等。对于这些尚未解决的问题，我们将在后面的章节逐步探索他们的解决方案。
内容概览
本书接下来的内容组织结构如下。第2章介绍基础知识，包括可证明安全基础、符号和术语以及几个密码学基础原语。在第3章，我们会介绍一个通用安全多方计算协议，并尝试更严谨地分析其安全性。第4章，我们将在探讨隐私性与恶意安全性的过程中，引出形式化模型——通用可组合框架。接下来，对每个协议我们都会给出形式化的安全定义，并严格证明协议的安全性。我们首先在第5章介绍茫然传输协议（包括半诚实安全和恶意安全）。然后，我们从半诚实安全的协议开始——第6章介绍基于线性秘密分享的协议，第7章介绍基于Beaver三元组实现的协议，第8章介绍基于混淆电路的协议。最后，我们在第9章介绍恶意安全的协议。
请读者注意，这些章节并非相互独立，而是紧密联系的。例如，第4章的通用可组合框架是基于对第3章协议的讨论而引出的；而第5章之后的协议的安全性证明，又基于形式化的通用可组合框架；最后，第9章的恶意安全的协议，也与半诚实的协议有着对应关系，它们在半诚实协议的基础上，使用不同的技术实现了恶意安全性。总之，我们的章节设置假设读者拥有了前述章节的前置知识，因此，强烈建议读者按照章节顺序依次阅读每一章。
本章思考题
一般来说，安全多方计算要求所有参与方对要计算的函数 \(f\) 具有共识，那么如果我们是否有可能让部分或者全部参与方在不知道函数\(f\)的情况下完成安全多方计算？如果可以，有哪些解决方案？如果不可以，为什么？
本章节中，安全多方计算的函数 \(f(x_1, …, x_n)\) 为确定性函数，请思考安全多方计算协议能否计算随机化算法或者概率函数呢？如果可以，如何实现？
除了参与方输入的隐私性和输出结果的正确性，一个安全多方计算协议在某些应用场景下是否还可能需要其他的安全特性？请举例说明。
学习笔记
记录协议细节、模拟器构造与图中记号对照。