2.3 基于安全多方计算的安全机制

安全多方计算（MPC）是密码学的一个子领域，目的是多个参与方协同地从每一方的隐私输入中计算某个函数的结果，而不用将这些输入数据展示给其他方。基于MPC，对于任何函数功能需求，我们都可以在不泄露除输出以外的信息的前提下计算它。MPC最初针对的是一个安全两方计算问题（即著名的“百万富翁问题”）而被正式提出的。

定义2-12 百万富翁问题 ^[289] 两个百万富翁都想比较到底谁更富有，但是又都不想让别人知道自己有多少钱。如何在没有可信的第三方的情况下解决这个问题？

该问题在1982年由姚期智教授提出^[289，290]，在1987年由Goldreich等人推广至多方场景^[109]，如图2-4所示。

当前主要有三种常用的隐私计算框架，可以用来实现安全多方计算^[284，25]，它们分别是：秘密共享（Secret Sharing，SS）^[253，234]，不经意传输（Oblivious Transfer，OT）^[110，154]，混淆电路（Garbled Circuit，GC）^[45，136]。

2.3.1 秘密共享

秘密共享（Secret Sharing或者Secret Splitting，中文又称为密钥共享）^[44，253]，最早由著名密码学家Shamir和Blakley于1979年分别提出。秘密共享是现代密码学领域的一个重要分支，是信息安全和数据保密的重要技术手段，也是安全多方计算和联邦学习等领域的一个基础应用技术^[23]。

直观来说，秘密共享就是指将要共享的秘密在一个用户群体里进行合理分配，以达到由所有成员共同掌管秘密的目的。秘密共享通过将原始秘密值A分割为随机多份，比如分割为n份，记为A₁，A₂，· · ·，A_n，并将这些份（或称共享内容）分发给n个不同的参与方，从而隐藏秘密值的一种概念。第i个参与方只拥有部分的秘密值A_i。当且仅当足够数量（比如至少t个）的秘密值组合在一起时，才能够重新构造被共享的秘密，而任意的t-1个秘密值都不能重构原始数据。

定义2-13 （t，n） 门限秘密共享方案^[250，253] 对于数据集合A，有n个用户集合（1，2，· · ·，n），一个（t，n）门限秘密共享方案包括分享（Share）和重构（Reconstruct）两个环节。

• 分享：分享是指借助一个算法M将原始数据m∈M拆分为n个部分（s₁，· · ·，s_n），并将它们分别下发给n个用户。

• 重构：重构是指借助一个算法F从n个用户中任意选取t个用户的秘密值，构成一个t元组，将这个t元组作为函数F的输入，能还原原始数据m∈M。更一般地，对于任意的m ∈ M，对于任意的t个用户集合（i₁，i₂，· · ·，i_t）⊆（1，2，· · ·，n），满足：

这里的t也被称为门限值。

当前的秘密共享方案研究，就在于如何高效地构造（t，n）门限秘密共享方案。这些方案包括算术秘密共享（Arithmetic Secret Sharing）^[77]、Shamir秘密共享（Shamir’s Secret Sharing）^[253]和二进制秘密共享（Binary Secret Sharing）^[274]等多种方式。

• t=1：这是最简单的形式，事实上，我们只需要将原始数据m∈M分发到n个用户即可。

• t=n：有多种方式可以实现（n，n）门限，较为常用的一种方案是，将原始数据m∈M编码为一个二进制表示s，对于前n-1个用户，任意生成和s长度相等的二进制表示s_i，s_i就是第i个用户的秘密值，对于第n个用户，我们将其秘密值设置为

• t=k：这种方案的实现形式有很多，典型的实现包括Shamir的基于拉格朗日插值法的实现^[253]。Blakley的门限方案则是利用多维空间点的性质建立的^[254]。有兴趣的读者可以查阅相关资料，这里不再详述具体实现过程。

在秘密共享系统中，攻击者必须同时获得一定数量的秘密碎片才能获得密钥，这种共享系统提高了系统的安全性。另外，当某些秘密碎片丢失或被毁时，利用其他的秘密份额仍然能够获得秘密，从而提高系统的可靠性。秘密共享的上述特征，使它在实际中得到了广泛的应用，包括通信密钥的管理、数据安全管理、银行网络管理、导弹控制发射、图像加密等^[23]。

此外，秘密共享没有中心节点的概念，因此有助于联邦学习的去中心化实现。文献[51]提出了基于秘密共享的安全聚合机制，用于保护横向联邦学习系统里的梯度和模型参数信息。

2.3.2 不经意传输

不经意传输（Oblivious Transfer，OT）是由Rabin在1981年提出的一种两方计算协议^[233]，被广泛应用于安全多方计算（MPC）等领域。

在不经意传输中，发送方拥有一个“消息-索引”对（M₁，1），···，（M_N，N）。在每次传输时，接收方选择一个满足1≤i≤N的索引i，并接收M_i。接收方不能得知关于数据库的任何其他信息，发送方也不能了解关于接收方i的选择的任何信息。

接下来，我们给出“n个中取1”不经意传输的定义。

定义2-14 “n个中取1”不经意传输^[269] 设A方有一个输入表（x₁，· · ·，x_n）作为输入，B方有i∈1，···，n作为输入。“n个中取1”不经意传输是一种安全多方计算协议，其中，A不能学习到关于i的信息，B只能学习到x_i。

当n=2时，我们得到了“2个中取1个”不经意传输（1-out-of-2不经意传输），“2个中取1个”不经意传输对两方安全计算是普适的^[140]。换言之，给定一个“2个中取1个”不经意传输，我们可以执行任何的安全两方计算操作。

研究者已发表了许多不经意传输的构造方法，例如Bellare-Micali构造^[46]、Naor-Pinka构造^[215]、Hazay-Lindell构造^[179]。

在实际应用中，不经意传输的一种实施方式是基于RSA公钥加密技术^[244，21]。举例来说，“2个中取1个”不经意传输的一个简单的实施流程如下^[21]。

• 发送方生成两对不同的公钥和私钥对，并公开这两个公钥，记这两个公钥分别为公钥pk₁和公钥pk₂。假设接收方希望收到消息m₁，但不希望发送方知道他想要收到的是消息m₁。接收方生成一个随机数k，再用公钥pk₁对k进行加密，并传给发送方。

• 发送方用他的两个私钥对这个加密后的k进行解密，用私钥sk₁解密得到k₁，用私钥sk₂解密得到k₂。只有k₁是等于k的，k₂是一个无意义的数。不过，因为发送方不知道接收方加密k时用的是哪个公钥，所以他并不知道解密出来的k₁和k₂中哪一个值才是真的k的值。

• 发送方把m₁和k₁进行异或，把m₂和k₂进行异或，并把两个异或结果都发送传给接收方。

• 接收方使用k与收到的消息进行异或。接收方只能算出m₁，而无法推测出m₂。这是因为接收方不知道私钥sk₂，从而推不出k₂的值，而且发送方也不知道接收方能算出哪一个消息。

• 接收方可以进一步通过校验信息（checksum，例如CRC校验码）来确定m₁是正确收到的消息。

2.3.3 混淆电路

混淆电路（Garbled Circuit，GC）是姚期智教授提出的安全多方计算概念^[22，289]。GC的思想是通过布尔电路的观点构造安全函数计算，使得参与方可以针对某个数值来计算答案，而不需要知道它们在计算式中输入的具体数字。因为GC的多方的共同计算是通过电路的方式实现的，所以这里的关键词是“电路”。实际上，所有可计算问题都可以转化为各个不同的电路，例如加法电路、比较电路、乘法电路等。而电路是由一个个门（gate）组成的，例如与门、非门、或门、与非门等。

混淆电路可以看成一种基于不经意传输的两方安全计算协议，它能够在不依赖第三方的前提下，允许两个互不信任方在各自私有输入上对任何函数进行求值。由于与、或、非门组成的逻辑电路可以执行任何计算，所以GC使用电路表示待计算函数。

GC的中心思想是将计算电路分解为产生阶段和求值阶段。两个参与方各自负责一个阶段，而在每一阶段中电路都被加密处理，所以任何一方都不能从其他方获取信息，但仍然可以根据电路获取结果。GC由一个不经意传输协议和一个分组密码组成。电路的复杂度至少是随输入内容大小的增大而线性增长的。

在GC发表后，GMW（Goldreich，Micali and Wigderson）三位学者将GC扩展使用于多方，用以抵抗恶意的攻击者^[110]。有关GC的更多信息，读者可以参考文献[283]。