SOK：安全多方计算的通用编译器

陆叁 2021-09-26

949

点击上方蓝字获取更多新鲜资讯

写在前面

翻译计划第二弹发布, 此次给大家带来的是《SoK: General Purpose Compilers for SecureMulti-Party Computation》文章的翻译, 相信对于研究MPC工程应用的小伙伴能够从中获取到有用知识信息.

感谢此次参与翻译的小伙伴: starry(摘要、第一章), 夕月一弯(第二章), 松山(第三章), 宋小宋(第四章、第五章)、Shirley杨(第六章-前五节)、林立可(第六章-后六节), 栾某人(第七章), 云中雨雾、六三(审稿)

摘要

安全多方计算（MPC）允许一组互不信任的参与方，基于其输入计算一个联合函数，计算期间不泄露除计算结果之外的任何信息。这种类型的计算非常强大，在学术界、工业界和政府有广泛的应用。用于安全计算的的协议已经存在几十年了，但是直到最近才有能在任意函数上执行 MPC 的通用编译器被开发出来。这些工作迅速提高了技术水平，并开始使得非专业用户能够使用MPC。然而这个领域变化太快，以至于即使是专家也很难能掌握最新框架的各种功能。

在本文中，我们调研了用于安全多方计算的通用编译器。这些工具提供了描述任意函数的高级抽象概念，并能执行安全计算协议。我们考虑了七个系统：EMP-toolkit，Obliv-C，ObliVM，TinyGarble，SCALE-MAMBA（原来的SPDZ），Wysteria，Share-mind，PICCO，ABY，Frigate 和 CBMC-GC。我们根据一系列标准来评估这些系统，包括语言的可表达性、加密后端的能力和对开发人员的可访问性。我们提出可改进 MPC 框架的文档，使其在社区内实现标准化，并对编译器未来发展方向提出了建议。安装和运行这些系统是具有挑战性的，对于每个系统，我们还提供了一个的完整虚拟环境（Docker容器），其中包含所有必要的依赖项，来运行编译器以及我们的示例程序.

I. 引言

安全多方计算（MPC）提供了一种机制，通过这种机制，一组数据所有者可以计算他们输入私有数据的联合函数，其中该协议的执行揭示的数据仅有输出，不会泄露底层数据的信息。MPC可以被看作是一种加密方法，用于提供一个可信方的功能，在互相不信任的情况下，该可信方接收参与方输入的隐私，计算一个函数并把结果返回相关参与方。由于这些强健的安全保证，MPC具有广泛的实际应用潜力，从安全的统计分析的通用计算 [23],[24],[26],[57],[58],[59],[60],[100]，到更特定的领域，例如金融监管 [2],[22],[27],[63]，生物医学计算 [38],[34],[80],[88],[86],[89],[136] 和卫星碰撞检测 [78],[79],[90].

尽管对MPC技术有需求，但实际应用却很受限。部分原因是其底层协议的效率问题。能够安全地计算任何函数的通用MPC协议，已经被密码界所熟知长达30年[33],[73],[131],[132]。至今，这些协议主要只具有理论上的意义，而且由于效率（从计算和通信复杂度的角度来看）太低而被认为在实际中没有用处。

为了解决效率问题，密码学者已经为各种应用场景，提出了高度优化的、专用的MPC协议。不幸的是，这些运作模型并不能促进MPC在实际中的广泛部署和应用。即使这些定制的 MPC 协议理论上足够高效，但是对每个应用来说，从设计、分析和实现定制的协议并不是一个可扩展的解决方案。

通用的 MPC 编译器，可以大大减少设计众多特定协议的负担，并可以让非专业人员快速地建模并部署安全计算。通过编译器这种系统的使用，可以让在使通用 MPC 协议实用并安全的工程投入的花费得到分摊。

当设计和构建一个MPC编译器时，出现了许多重大的挑战。一般来说，强健和高效地和实现任何类型的多轮、分布式的协议是一个重大的工程挑战，但是MPC编译器有额外的需求，这使得正确地构建它们特别具有挑战性。为了提高效率，编译器和加密后端都需要高度地优化。为了提高可用性，编译器的前端需要对非专业人士具有表达性、灵活性和直观性，并且应该把底层MPC协议的复杂性抽象化，其中包括电路级别的优化（例如用布尔电路实现浮点数操作）和后端协议选择（例如为特定的计算选择一个最优协议）。对于如今存在的编译器，优化性能通常仍然需要用户具备大量的知识储备和努力。

Fairplay [103] 是第一个公开可用的MPC编译器。它能用高级安全函数定义语言（SFDL）编写的代码转换为混淆电路表示，然后可由双方（安全地）对其进行评估。通过使用了修改版本的 BMR 协议[10]，Fairplay 被扩展成能实现真正的多方计算的 FairplayMP[15]。随后，VIFF [68],[50] 和 SEPIA[29] 也相继被提出，它们使用相同的基本架构，用高级语言编写程序，将其转换成电路格式，并使用安全计算协议执行电路。

这些早期的编译器表明通用的 MPC 是可以实现的，尽管它们的性能致使它们不适合大多数现实世界的应用。但他们在 MPC 编译器的设计和实现方面开创了一个非常活跃的研究领域。

由于这些努力，安全计算算法的显著改进以及硬件算法性能的稳步提高，使得 MPC 成为大量现实世界问题的可行解决方案。最新的MPC协议实现速度足够快，可以在中等规模的数据集上安全地执行复杂的函数，例如使用数万到数十万的观测量以及数十到数百个变量实现安全地回归分析[24],[41],[67],[91],[108]。

这一领域的大量的活动可能难以驾驭：数十个新的编译器和支持框架包含各种各样的架构和特性，这些架构和特性影响了它们的效率、可用性和对不同任务的适用性。这篇知识系统化论文的目的是为强大的新一代MPC编译器提供一个指导，主要针对四种不同类型的读者：

希望选择一个编译器来实现特定的安全计算的开发人员；
需要了解最新的实用和安全的计算技术的理论密码学家；
希望了解现有技术的局限性并确定新研究方向的编译器设计者；
需要了解现有技术是否足够成熟来满足他们的需求的管理者和决策者。

本文简要地回顾了安全多方计算的必要技术背景，然后调研了目前最先进的MPC框架，并从其总体框架、底层技术、威胁模型和表达性等方面对其进行了评估。我们的比较重点在于可用性而不是性能指标上，并且我们通过在每种情况下实现三个小的测试程序来展示我们的实验。非专业的读者可能希望略过深入地讨论每个框架的第六节，而直接关注最后的讨论部分，在那里我们提倡改进文档以及标准化，并提出了编译器研究的未来方向。

许多框架本身就是研究项目或正在进行的工作：它们具有重要的构建依赖关系和复杂的工作流。实际上，在每个系统中实现我们的简单示例程序需要大量的工程工作：我们估计超过750人时。为了让其他人更容易地试验这些系统，我们创建一个在线Github仓库，它带有两个组件：（1）一组Docker容器，每个容器都配置了每个MPC框架的软件基础设施以及我们测试用例的开发环境。（2）一个Wiki页面，它收了这里提到的许多评估，以及关于每个框架的附加档案。

II. 密码学基础

本节主要介绍许多MPC协议共有的重要密码原语。

A. 秘密共享

密码学秘密共享协议[120]、[21]允许交易商将秘密值分解为份额并将这些份额分发给具有以下属性的接收者集合：任何不合格的接收者集合对秘密一无所知，而任何合格的接收者集合可以从他们的份额中重建秘密。在实践中，大多数秘密共享协议都是阈值协议，其中任何少于份的集合都不会透露任何关于秘密的信息，任何大小至少为的子集都可以重建秘密。存在许多通用秘密共享方案 [18]、[28]、[20]、[125]、[45]，以及用于通用（非阈值）访问结构的秘密共享方案的构建 [69]、[81]。有关秘密共享协议的综述，请参阅Beimel的文章[12]。

在实践中，大多数MPC协议依赖于线性秘密共享方案：或是简单的加法秘密共享，或是Shamir共享。两者都满足线性性质：即两个秘密份额的总和等于总和的份额。

B. 不经意传输（OT）

不经意传输（OT）[114], [130], [62] 是一种加密协议，其允许一方从另一方的个秘密中选择个，但不透露所选择的秘密。图1显示了 -OT，表示从两个选项中选择一个秘密。

从理论角度来看，MPC协议可以单独由OT构建[95]、[84]，但使OT适合构建高效 MPC协议的关键特征是，OT等价于一个看似较弱的功能，称为随机OT（ROT）[46]，其中选择比特位不是提供为输入，而是由协议本身随机生成的。ROT协议的输出是两个相关的比特对和，其中，，在上均匀分布。给定一个随机的OT相关性（和），Alice 和 Bob 可以仅使用三比特位的通信就能计算 OT 功能。

由于 ROT 隐含 OT，因此各方可以在独立于输入的预处理（“离线”）阶段提前计算协议所需的所有必要 ROT。然后，在“在线”阶段，他们消耗这些预先生成的 OT 并以最小的通信成本和没有计算成本的公钥操作来执行协议。这种离线-在线分离使得这种协议的在线阶段非常高效，但仍然存在使预处理阶段高效的问题。有两种根本不同的方法来处理离线阶段，要么通过受信任的交易商，要么利用一个批处理的加密相关性生成协议。

在可信交易商模型中，一个半可信交易商简单地将相关随机性分配给所有各方。可信交易商自身没有输入，也从不处理任何秘密信息，因此交易商只需要被信任以生成并向其他合适的各方分发随机值。在有可信交易商的情况下，许多MPC协议的离线阶段可以非常有效。

即使没有可信交易商，也可以通过OT扩展（OT-extension）来有效地生成OT，即通过使用高效的对称密钥原语（如，AES），将少量的 "base" 或 "seed" OTs 转换成大量的 ROTs [83]。自从 OT 扩展（OT-extension）提出以来，已经有许多 OT 扩展的变种 [7]、[84]、[77]、[107]、[98]、[93]，并且 OT 已经成为几乎所有 MPC实现中的一个重要特征。

III. 安全多方计算

安全多方计算协议 (MPC) 允许一组相互不信任的利益相关者，安全地计算他们联合输入的任何函数，其方式是协议的执行可以证明除了计算的结果之外，没有任何别的信息被泄露出来。安全性通常使用模拟范式来定义，如果存在有效的（多项式时间）模拟器，该模拟器将计算的输出作为输入并生成协议 transcript（每个参与者的“视图”），使得任何视图（或视图的某些子集）与由协议的实际执行创建的 transcript 无法区分，则称该协议是安全的。

这确保了每个参与者（或某些共谋参与者的子集）从执行协议中没有学到任何他们无法单独从输出中学到的东西。通过这种方式，MPC以加密方式模拟了一个可接受每个参与者秘密输入的可信方，它计算所需的函数并返回结果。

早期的 MPC 协议使用电路模型来实现安全计算，首先把目标函数表示成布尔电路或算术电路（某个有限域上的），然后逐门安全地估算该电路。我们分析的许多编译器仍然使用这个计算电路模型。在该章的剩余部分，我们概述支持现代 MPC 系统主流协议族的关键设计特征。

A. 乱码电路（混淆电路）

电路乱码是保证两方安全的一种计算方法，最初由 Yao [131]、[132] 引入。在这个框架中，有两个参与方，一个Garbler和一个Evaluator。这两个参与方首先把所需函数表示成布尔电路。Garbler然后继续该进程，它使用标准对称加密系统（通常是 AES）对该电路的逐个门进行乱码混淆，过程如下。对于该电路中的每条线路，Garbler随机均匀地选择两个独立的“线路令牌”。然后，Garbler 通过加密基于两个输入线路令牌产生的输出线路令牌，把该电路中的每个门表示成一个真值表（对于具有两个输入端的布尔电路，每个真值表将由四行构成）。Garbler把真值表的所有行进行置换，并将所有的“乱码”门发送给Evaluator。乱码程序是这样设计的，它可以实现：如果对该电路中的某个门，你可以获得该门每个输入线路的线路令牌，那么你就能够确切解密该门的乱码真值表的一行，从而泄露该门输出线路的单个线路令牌。因此，Evaluator通过获得该电路每个输入线路的单个线路令牌，就可以为每个线路迭代生成线路令牌，进而全面估算该电路。

为了给Evaluator提供秘密输入，Garbler直接给它发送正确的线路令牌。对于Evaluator的所有输入信息的每个bit，Garbler和Evaluator参与一个不经意过程，在其中，Evaluator秘密地选择由 Garbler提供的两个线路令牌之一。当Evaluator对每个输入bit都拥有一个线路令牌，它就可以评估该电路值（为每个门执行基于对称密钥的解密）并获得结果。在半诚实模型当中，Evaluator把计算的结果转发给Garbler。对于乱码程序的正式描述，请参阅 Bellare 等人的工作[14]。

最初的乱码电路协议提供了对抗半诚实的敌手的安全性 [99]，但存在许多不同的改进和实现，它们提供了针对完全恶意敌手的安全性。

两个关键的性能改进是，free-XOR [97]，它在单轮内估算异或门没有利用乱码表所需的任何加密操作；和 Half-Gates [134]，它们减少了乱码 AND 门所需的密文数量。AES-NI 指令集的加入使得计算现代处理器上的 AES 加密非常高效，并大大减少了计算基于乱码电路的协议的成本。

乱码电路在密码学中是如此有用和无处不在，人们认为电路乱码应该被视为一种基本的密码学原语（如加密或签名），而不仅仅是作为一种用于两方安全计算的协议 [14]。

主要特点：电路乱码本质上是两方协议，并且只需要恒定数量的多轮通信（独立于电路深度）。（昂贵的）公钥操作的数量仅取决于输入大小（OT 是公钥原语），并且私钥操作的数量取决于门的数量。总通讯成本与电路的大小成正比。由于乱码电路协议用真值表表示每个门，当对算术电路进行乱码时，电路大小与域大小成二次方增长。于是几乎所有的乱码电路协议在布尔电路上进行运算。也有一些在大的域上对算术电路进行混淆的不同方法 [4]，但这些从未实施。

B. 基于多方电路的协议

GMW [73]、BGW [17] 和 CCD [33] 协议允许任意数量的参与方安全地计算表示为电路的函数。在这些协议中，每一方使用线性秘密共享方案来共享它的输入，各方参与一个协议来逐门地计算答案。每个门计算安全地将门输入的秘密份额转换为门输出的秘密份额。对于该电路中的每个加法门，各参与者利用秘密共享方案的线性特点来局部计算输出的份额。估算乘法门需要通信，并且这些方案在处理乘法的方式上有所不同。

GMW 协议可以估算布尔电路或算术电路，并通过如下方式执行乘法门：对布尔电路使用不经意传输协议，对算术电路使用不经意多项式估值 [106] 或不经意线性估值 [56]。见Ishai等人的工作[85]，总结了一些安全计算乘法门的不同方法。

乘法门的不经意通信主导了电路计算的开销。所有实用的基于GMW 的协议实现已采取措施减少他们的开销。无论是计算算术电路还是布尔电路，方法是一样的：在离线预计算阶段，参与者产生相关的随机性（或从受信任的中介处接收），而在在线阶段，他们使用这些随机相关性作为掩码或一次性填充，基于输入的秘密份额来计算乘法门的输出的份额。

基于布尔电路 GMW 的协议使用 OT extension [83] 来预先计算 ROT 相关性，以便在协议的在线阶段使用。基于算术电路 GMW 的协议通常会生成某种形式的 “ Beaver 乘法三元组”（随机三元组的秘密共享( ; ; ),，其中是域元素) [11] ，其在在线阶段被用作掩码。

信息理论协议，如BGW[16]和CCD[31]依赖于支持强乘法的秘密共享方案[40]、[33]、[29]、[41]，而不是公钥原语。这些协议可以更快，因为它们不需要计算上昂贵的公钥操作，但需要大多数参与者诚实。它们通常不会从包括协议的预计算阶段中获益

主要特点：基于多方电路的协议可以支持任意数量的参与者。通信轮数与该电路的乘积深度成正比，而且通信的总量取决于该电路中乘法门的数量。这些协议允许独立计算方，在不影响安全的情况下，接收输入并将输出传递给其他参与方。

C. 混合模型

最近的系统已经摆脱了严格的电路表示法，而是采用了混合模型，将常见操作的优化子协议拼接在一起（可能使用传统的基于电路的操作）。这些混合系统通常将中间值表示为一个大的有限域的秘密份额。他们可能会混合使用信息论协议和加密协议，因此，计算方的数量和威胁模型也不同。

混合模型允许与严格的基于电路的模型有非常不同的性能特征。例如，在一个有限域中，像比较、位移和平等测试这样的操作在表示为算术电路时很昂贵。然而，对秘密共享进行操作的专门子协议（例如，[44], [45], [39]）可以更有效地计算出共享的结果

D. 替代方法

全同态加密 [71] 提供了一种针对被编码为算术电路的函数的安全计算替代方法。有几个函数库实现了全同态加密，包括 HELib [76]、PALISADE [118] 和 SEAL [117]。我们的确没有把它们包括在我们的对比当中。还有一些工作是针对 RAM 模型程序进行混淆的 [102]、[72]、[66]、而不是针对电路，但这些工作还没有被实现。

IV. 框架调查

我们调研了11种通用的安全多方计算编译器框架，这些框架都遵循以下相同的通用方法：首先，编译器使用专业的高级语言把安全多方计算程序转换成一个中间件（通常为电路）。然后，这个电路作为输入传给，这个用于执行多方安全协议和生成计算结果。同时，我们也调研了两种没有组件的编译器（Frigate 和 CBMC-GC）。

表I展示了这些框架的基本信息，其中包括协议类型，安全设置，可用性和一些可使用性特征，例如：文档等。其次，我们把工作范围限定在：自2014年以来，具有重大更新工作的框架上。我们没有考虑框架的实现：所有的工作都包含一个开发的前端。我们也不考虑与安全计算相关的标准库和 API。在很多情况下，我们只考虑一个研究小组的最新工作。

这些框架通常在学术的、同行评审的论文中介绍过。尽管许多人开发了自定义或优化的协议，但我们将它们广泛地分组到协议族中，如部分所述第三章。混淆电路 (GC)、多方电路协议 (MC) 和混合模型 (Hy)。我们还注意到在协议评估中可以多方支持计算的参与数量。

我们确定了两种主要的威胁模型：一个是半诚实者模型：半诚实的对手正确执行协议，但试图从他们收到的数据中收集额外的信息。另一个是恶意攻击者模型，恶意攻击者可能会任意破坏协议以了解有关其他输入的信息或导致协议输出错误结果。在实践中，针对恶意对手的安全性实施为“恶意中止”方案，如果检测到恶意活动，协议将中止；恶意的对手不会导致错误的答案，但可能会导致根本没有答案。这些描述符不适用于不执行安全计算的框架。我们注意到该框架是否允许混合模式计算：一种在单个程序中同时执行安全和不安全操作的方法。

在所有表格中，部分支持由符号

表示。这些限制将在后面的文本中详细解释.

A. 工程挑战

许多协议使用基于电路的模型来表示将要计算的函数。这样做的优点是基于电路的计算是独立于输入的，因此协议的运行时间不会泄露任何关于用户输入的信息。然而，使用电路模型会带来严重的挑战和限制，这些挑战和限制在我们测试的所有框架中都有一定程度的表现。

算术电路在一个有限域上操作，这个有限域的大小必须事先设定，而且必须大到足以防止溢出（这将因应用而异）。算术电路本身不支持非算术运算，如比较和相等检查。

布尔电路需要为每个位宽（bit width）重新定义基本操作：在这样的协议中支持位整数的算术需要实现位加法和乘法电路。我们发现在这个领域没有标准化，大多数布尔电路编译器设计和实现他们自己的算术运算。这导致了对可接受的程序的许多限制，而且大多数基于布尔电路的框架不支持任意位宽的运算。

将高级程序编译成电路需要展开所有循环和递归调用。对于隐私性，循环迭代的次数和递归深度不能依赖于隐私输入。在某些情况下，静态分析技术可以推断循环终止条件，但大多数编译器不支持这种分析，相反需要强制程序员在编译时手动定义循环边界。但是，很少有编译器支持递归操作。

秘密数据的条件操作能够显示：可以根据分支上的计算量不同区分具体哪个分支，因此它们通常被实现为多路复用器，其中，它们会对两个分支进行评估。同样，私有索引上的简单数组查找必须扩展到线性大小的多路复用器电路。Frigate, CBMC_GC, 和 PICCO 就是以这种方式实现隐私索引的。Oblivious RAM [74] 提供了一种可以通过RAM 独立访问模式数据的方法，但是很少框架会有编译库或者天生支持 ORAM 访问模式。大多数语言甚至不允许语法上的私有数组索引：如果是一个 “秘密” 整数，而是一个“秘密”数组，那么是无效的语法。

平衡透明度和灵活性是MPC编译器设计者的一个关键挑战。MPC协议通常与相应的不安全计算有非常不同的性能特征，为了提供更多的、有表现力的高级语言而对最终用户完全隐藏这些差异的编译器（如自动多路复用）会导致开发者写出不 "MPC友好 "的代码。另外，一个提供对不同后端表示的直接访问的框架，假定最终用户具有高度的密码专业知识，但允许专家用户编写高度优化的MPC协议。通过为代码的不同部分自动选择最佳的MPC协议，有可能同时提供表达性和协议效率，而不需要开发人员有高度的密码知识。然而，这种类型的自动优化是困难的，我们分析的MPC编译器并没有尝试这样做。EzPC项目[30]和ABY3项目[100]，都是基于ABY（第VI-F节），试图在三种协议中自动优化后端表示。然而，在写这篇文章的时候，这两个项目都没有可用的代码，我们没有把它们纳入我们的测试中。

V. 评定标准

A. 可用性

我们考虑开发人员使用该框架安装、运行和编写程序所需的工具和文档。我们的发现总结见表一。我们确定了几种类型的有价值的文档。值得庆幸的是，我们测试的每个框架都包括某种形式的基本安装文档。语言文档提供了高级语言的概述：语言架构和设计文档、入门指南或教程，或生成类型和内置函数的列表。一些较大的系统也有在线支持，例如活动邮件列表或提供技术支持的付费人员。功能示例代码演示了框架内程序的端到端执行，通常比一般语言文档更新(a表示我们需要额外的文件或工具来运行示例)。显式示例文档提供了这些程序的上下文，无论是在代码注释中还是在单独文档中（a表示受限文档；见第VI节中的详细信息）。大多数框架都是标准GNU或BSD许可下的开源框架（a表示完整功能需要闭源代码工具或代码）。我们记录了最后一次重大更新的日期（截至撰写本文的日期）：包括正在进行的开发或最新的标记发布。

B. 示例程序

我们实现了三个示例程序来评估框架的可用性、表达性、体系结构和密码设计。除了我们的在线服务在存储库中，我们在附录A中包括说明性代码示例。

三方乘法：这个程序从三个参与方中获取整数输入并计算其乘积。这个简单的函数演示了每个框架的结构。该程序测试实现是否支持三方或多方，或者是否有一种简单的方法来可以在两个计算服务器上秘密共享多个输入。它还测试了该框架的基本数值能力：整数的输入和输出，以及对安全类型的简单计算。
内积：内积取两个向量元素两两乘积之和。它测试与数组相关的功能。各方应能够将数组作为输入传递，在其中存储秘密数据，并访问和迭代内容。一些框架提供了通过显式语法支持，或者通过像SIMD门这样的并行架构设备来并行化数组计算的方法。
交叉制表：交叉制表程序按类别计算平均值，其中类别表和值表共享一个主键，但由不同的各方所有。这个测试框架的表达能力，包括输入、输出以及对秘密数据的数组和条件的修改。在某些情况下，我们测试了是否支持用户定义的数据类型（结构）。我们使用了一个简单的蛮力的算法，并且通常按类别返回总和的列表（而不是平均值）。

C. 功能性

我们评估了用于定义安全函数的高级语言的表达能力。这些标准的汇总情况见表二。

数据类型：完全支持的数据类型必须同时具有公共形式和秘密形式，并且该语言应允许该类型的输入和输出。这些值包括布尔值、有符号或无符号固定长度整数，以及更复杂的数值类型，如任意长度整数和浮点数或定点数。虽然这些类型的库可以使用固定长度的整数类型来构建，但我们仅在默认情况下可用时才会将它们标记为支持。组合类型包括数组和动态数组，其中后者的大小在编译时未知，结构、可以将其他数据类型作为子域的用户定义类型也是如此。如果这些复杂类型可以包含安全数据，则它们被标记为支持。
运算符：受支持的运算符可以应用于秘密数据类型，以获得秘密结果。我们考虑布尔矩阵上的逻辑算子和整数之间的比较（等式和不等式）。我们将加减法归为一类，并分别分为乘法和除法。我们考虑两个比特级运算：固定长度整数上的比特移位和按位运算。
语法：秘密布尔条件上的条件可以用if-语句语法或多路复用器运算符来实现，尽管我们需要一个显式的语言构造。我们考虑了具有公共索引的数组访问，以及更难的具有私有索引的数组访问问题。后者可以通过线性时间多路复用器(Mux)、本机ORAM支持(ORAM)或ORAM库(Lib)实现。

D. 实施标准

在本节中，我们定义了架构和加密标准，总结见表三。我们注意到了每个框架的主要开发语言。混淆电路协议可以通过使用AES-NI来显著提高性能，它是x86指令集的扩展，可以加速AES的加密和解密。

体系结构：我们定义了三个广泛的体系结构类别。独立的框架开发新的语言和编译器：从受限的、特定的领域与现有通用语言接口到独立环境的语言。一些框架是现有语言的扩展。这些操作可能会修改或扩展现有的编译器以添加功能，或将编译器中间状态作为输入。库框架完全以现有语言实现。它们通常为电路构造和协议执行定义了一个安全的类型类和方法.
计算模型：我们考虑底层的计算模型是基于算术域，还是基于布尔电路。混淆电路实现可以动态生成电路，在电路完全生成之前开始运行时执行。这可以减少资源消耗，允许动态数组和循环边界，并减少整个程序运行时间。
输入/输出(I/O)：输入通常是从文件中读取的，但某些框架允许任意格式，而不是特定的输入格式。（我们已经为示例程序生成了输入生成脚本。）我们注意到该框架是否支持来自各方的不同输入类型。框架应支持数组输出（a表示数组元素必须一次返回一个）和多个输出，其中一方在单个计算中接收两个或多个输出值（a表示多个值必须封装在一个结构中）。

在第VI节中，我们专门讨论了I/O文件格式中的限制，包括支持任意大小的整数。我们认识到，许多框架都是在学术环境中产生的，它们可能不重视“工程问题”，如I/O，但我们发现，这些功能对可用性的重大影响使它们值得在本调查中讨论。

E. 性能

在这项工作中，我们关注于可用性，而不是框架性能的基准(如运行时间、带宽、内存使用情况、电路深度）。我们相信，对我们的样本项目进行定量评估并不能准确地进行表示每个框架的性能能力。理论效率指标并不总是适用于实际的MPC体系结构有几个原因，我们发现不同模型之间的直接比较往往具有误导性。电路的大小和深度在混淆电路和基于秘密共享的协议中有不同的含义，而且许多框架从未生成完整的电路进行比较。执行时间因框架体系结构而异，预处理阶段和执行体系结构中的其他变化进一步使时间测量更加复杂化。

协议系列和威胁模型的变化意味着大多数框架都不具有直接的可比较性，而且我们对基准测试功能的选择将对框架的相对速度产生重大影响。我们的示例程序被设计用来揭示一个框架的表达能力，并不一定代表一个实际的MPC用例。对我们的一个程序的单次运行的独立测量不会考虑到可以在实践中评估安全计算的上下文（通常是更大系统的一部分）。

我们不希望通过为不切实际的测试用例提供具体的数字来破坏不可比较的框架。虽然这是一项有价值且实用的努力，但产生一个实际的测试框架已经超出了本项目的范围。

VI. 框架

A. EMP toolkit

EMP toolkit [126] 是基于混淆电路的一整套MPC框架。该工具包的核心内容包括：不经意传输库、多种类型安全的类以及几个自定义协议的实现。我们测试了两个协议：一个是半诚实安全的Yao氏混淆电路协议( Yao's Garbled Circuit )的实现，另一个是恶意安全的，可验证混淆电路协议( Malicious Authenticated Garbling )[128]。该工具包包括三个我们没有研究的恶意安全协议：一个可检查输入有效性的两方计算协议[92]，一个两方计算库[127]，以及一个多方计算协议[129] 。

a) 半诚实：Yao氏混淆电路协议由定义了类型安全的类和操作的C语言库实现。我们发现其对非专业的C语言开发者比较直观。该库的结构使得开发者可以使用C语言的数组和结构来保存安全值，并且提供简单的混合模式计算并能即时生成对应的电路。

EMP toolkit框架支持任意长度的整型数和浮点数。任意大的数值都可以由字符串进行初始化，并以类似的方式返回；它们不限于C语言类型。该框架没有明确的语言文档，但代码相对清晰。此外，该库可以输出一个与协议无关的电路，这一点没有被记录下来。

b) 恶意安全的可验证混淆电路：这个库主要实现了一个自定义的混淆协议。我们能够运行库里预编译的电路例子和我们自己设计的一些例子。然而，它支持的功能是有限的：函数必须提前编码为一个电路，然后再使用半诚实可信的库进行计算，并且电路的输入/输出都由布尔数组的方式进行编码。

建议：我们推荐使用EMP-toolkit半诚实库。由于可用的电路生成和密码库，整个平台非常适用于学术研究，研究实现一种基于电路的新协议。但是我们发现该库中端到端的流程不是无缝的。

B. Obliv-C

Obliv-C是一个C语言的扩展，可执行一个两方的混淆电路协议。其中主要的扩展是一个obliv类型限定符，用于C语言类型和结构。类型规则使得obliv类型必须保持秘密的，除非明确可以公开。在oblivious函数和条件中的代码不可以修改公共数据，除非是在限定的*~obliv*块中，在该块中的代码总是能够被执行。这些规则允许程序员对数据安全进行推理，并开发模块数据库。

编译器将这些扩展的功能和其所支持的C语言代码结合起来，生成一个可执行文件。该可执行文件可以即时转化为一个电路。这使得电路的大小取决于编译时不知道的数值，但可能导致电路优化程度不够。

我们成功地使用了一个Obliv-C的ORAM库，Absentiminded Crypto Kit。该库实现了几个ORAM的变体和一些其他有用的原语[135]，[55]。

Obliv-C扩展了C语言，但是许多例子都证明了其独立语言结构，可以将Obliv-C代码与C代码区分开。实例程序通常用本地的C代码读取、处理和输出数据，Obliv-C代码中只执行安全计算。然而，这种抽象机制并不是强制的：可以在Obliv-C文件中执行输入/输出和调用本地的C函数。虽然许多例子在支持C代码和安全的Obliv-C代码时实现了严格的分离，但示例文件采用了混合的模式。

有几个小组已经使用Obliv-C实现了一些安全函数，包括：线性回归[67]，分布式证书颁发机构[87]，聚合的隐私机器学习模型[123]，加密电子邮件分类[75]以及稳定匹配[54]。

建议： Obliv-C是一个强大的混淆电路框架。我们把它推荐给一般的开发者和希望实现和优化一些有用的库（例如ORAM）的学者。

C. ObliVM

ObliVM，编译了一种名为ObliVM-lang的类Java语言，并可以执行一个两方的混淆电路协议。它的目的是为非专业人士提供一种直观的语言，并同时实现特定领域的编程抽象机制，用于提升性能。

ObliVM-lang允许用户自定义数据类型和类型推断。它实现了一个内置的高效ORAM方案。ObliVM原生地支持固定大小的整型数，并包括一个用于任意大小的整型数的库。

然而，该库的说明文档有限，无论是针对语言（我们发现了几个未记录的保留关键字），还是一般的用法。输入/输出是有限制的：它需要一个非人类可读的格式，而且我们无法编写一个返回结果为复杂类型（包括结构和数组）或者超过32比特的计算函数。此外，我们也没有实现串联的例子。

建议：尽管ObliVM实现了先进的密码结构，但由于其极少的说明文档和受限的输入/输出功能，使得其在实际应用中的可用性受到限制。

D. TinyGarble

TinyGarble[122]利用硬件电路生成工具来创建适合混淆电路协议的优化电路。它需要三个步骤：首先，需要将Verilog中定义的函数转化为网表格式；然后，将网表格式转化为一个自定义电路描述（SCD），并采用混淆电路协议安全地评估布尔电路。

我们发现，这个过程的第一步需要一个闭源的逻辑综合工具（Synopsys Design编辑器）来将Verilog文件转化为非标准化的网表格式。TinyGarble的作者参考了一个开源的工具，Yosys Open SYnthesis Suite，但是我们无法编译任何例子（从Yosys生成的网表格式文件到SCD的转化失败）。TinyGarble的源码包括一些预编译好的网表格式文件。虽然我们可以看到这些例子的每个步骤（Verilog源，网表文件，计算输出），但是我们无法对这些文件进行端到端的编译。因此，我们不做任何有关于语言功能的结论。

TinyGarble的前身是JustGarble[13]，一个用于电路混淆和评估的库。JustGarble并不包括通讯和电路生成。TinyGarble中混淆电路的实现在JustGarble的基础之上做了严格的改进。TinyGarble后续产品[51]利用了硬件逻辑综合工具来对GMW相关的计算进行优化。

建议： TinyGarble旨在利用为生产硬件而开发的强大的电路优化器，然而，从实用性的角度来看，TinyGarble缺乏对Verilog编译器的兼容性，以及缺乏网表格式的标准，这意味着我们无法使用TinyGarble框架编译或运行任何新的例子。但是，我们相信MPC社区仍然可以通过从现有的电路优化器的能力中收益。

E. Wysteria

Wysteria[115]介绍了一种新颖的高层的functional编程语言。它作为一个可信方，保证了一个分布式的安全计算并产生一样的输出。Wysteria支持任意数量的参与方，并且其软件的贡献包括：一种前端语言、一个类型检查器和一个执行基于布尔电路的GMW协议的运行器解释器。

Wysteria通过叫secure block的一种语言结构来支持一种混合模式的计算。一个secure block被初始化为一组参与方和他们对应的输入。在block中所有的操作都被编译成一个布尔电路，并且作为单独的计算进行执行操作。

从这篇文章发表以来，Wysteria的代码库已经发生了变化，论文中提出的例子并没有被编译。然而他们对工作程序的结构提供了一些有用的背景。项目仓库中包含有几个例子程序，并且运行无错，其中包括一个六方版本的百万富翁问题。

Wysteria包含一个记录类型，该类型持有其他类型的命名值，并且可以从secure block中安全返回。尽管 Wysteria包括将数组输入到secure block的工作实例，但我们无法将其应用到我们的内积计算或者交叉表程序中。该语言支持在 secure block 中对数组进行迭代，并允许访问secure block之外的数组元素。然而，我们遇到了其他的语言限制：Wysteria 只支持在secure block中除以2，并且我们没有找到在布尔上使用逻辑运算符的方法。

Wys*[116]项目建立在Wysteria的思想之上，并且试图在F*编程语言的基础之上为安全计算建立一个全验证工具链（fully-verified toolchain）。然而F*语言现在正处于快速发展阶段，我们无法编译Wys*。

建议： Wysteria支持的复杂数据类型有限，目前缺乏开发，并且后端采用的电路解析器已经过时，这也意味着它不适用于开发复杂或者高效的协议。另一方面，我们研究中，唯一计划为其提供一个验证系统的就是Wysteria编译器，该系统用于自动验证底层多方计算与开发者实现的单体式应用程序具有相同功能，此外，Wysteria也是唯一一个具有函数式编程语言的编译器。我们建议未来的编译器开发者使用Wysteria中基于类型的正确性和安全保证作为模型。

F.ABY

ABY[53]是一个混合协议的两方计算框架，基于 C++ 库来实现。它的目的是通过提供一种混合协议的机制，给予开发者对计算效率的细粒度控制。ABY 在三种协议之间切换：基于算术协议的 GMW 在算术电路上使用基于乘法三元组的加法共享方案。该协议基于[8]，[94]，[113]。其他协议使用布尔电路：布尔协议采用了一个基于 XOR 的共享方案实现了原始的 GMW 协议，而姚氏协议使用了姚氏混淆电路协议的优化版本。

ABY 有大量的文件，这些文件提供了一个有益的框架来理解 ABY 的能力。这包括一个稍显过时的开发者指南，一个扩展的 README 文件，以及各种评论性的例子。

安全数据仅限于无符号 C 整数类型。ABY 不支持任意长度的整数或明确的布尔类型，尽管它允许一个位的功能相当的整数。它支持一些浮点运算，并且正在积极开发这一功能。ABY 可以在一个 C 结构体中存储安全数据，并支持支持 C++ 数组和 SIMD 结构以实现高效的并行操作。ABY 提供的功能用于创建和填充SIMD "共享"，但检索单个的元素需要对秘密数据的内部表示进行操作，而这并没有得到很好的支持。

ABY 已经被用来实现一些安全计算系统 [3]、[36]、[37]、[52]、[96]、[112]。

建议： ABY提供了一个强大的、低级别的加密接口，使开发人员能够对性能进行显著的管控。ABY 是针对那些熟悉 MPC 协议和计算电路模型的用户。我们推荐它给具有足够密码学背景的开发者。

G. SCALE-MAMBA

SCALE-MAMBA 实现了一个恶意安全的的两阶段混合协议，并取代了 SPDZ 框架。MAMBA 是一种类似于 Python 的语言，可以编译成字节码表示。SCALE 实现了一个两阶段的协议，这个协议将所有的公钥操作转移到一个离线的预处理阶段，并且生成了三种类型的共享随机性，执行了一个优化的混合协议，这个混合协议基于先前的工作 [19], [49], [107]。

SCALE-MAMBA 有大量的文档，涵盖了与以前的 SPDZ 系统的区别、安装和运行说明、更新的语言文档，以及协议原语。示例程序是单元式测试，但没有明确的文档。一个社区公告板（groups.google.com/forum）主持关于该框架的讨论和问题。

SCALE-MAMBA 框架允许开发者来定义他们自己的 I/O 类。这提供了一个极其灵活的接口。我们没有实现一个自定义的I/O类。该框架的安全通道设置要求用户产生一个小型的证书授权，以便运行一个计算。

用一个简单的全阈值秘密共享方案运行我们的示例程序，需要大量的内存资源。然而，该系统为秘密共享方案提供了多种可定制的选项，以及包括在某些情况下生成离线数据的程序化工具。为了实现测试目的，SCALE 包括了使用假的（不安全的）离线数据运行的选项。

整数大小是由字段大小决定的，而字段大小必须在编译时确定。标准的全阈值共享支持高达1024位的模数。SCALE-MAMBA 支持大多数位移操作，并且包括 Python-style 元组，我们认为它是一种不太强大的结构类型。SCALE-MAMBA 完全支持定点数，部分支持浮点数。它还支持ORAM，但我们没有测试。

建议：我们推荐 SCALE-MAMBA 用于各种用途：它是灵活的，支持任意数量的参与方，并有强大的安全保证，尽管它可能需要大量的计算资源。

H. Sharemind MPC

Sharemind[25] 是一个安全的数据处理平台，也是 Cybernetica 的商标，Cybernetica 是一家专注于研究和开发的技术公司，总部设在爱沙尼亚。我们使用 Sharemind MPC平台，它可以安全地执行用 SecreC 语言编写的函数。该框架使用加法秘密共享方案，执行了一个三方混合协议。

Sharemind MPC 平台明确地定义了三方：负责输入数据的客户端；负责定义和运行安全计算的服务端；负责接收安全计算输出的输出端。服务器代码是用 SecreC 语言编写的，并使用Sharemind 的安全运行时执行，而客户端和输出端代码则使用通用编程语言的客户端库，以及使用标准编译器执行。我们使用 C 语言的客户端库开发了我们的示例程序；该平台也提供了Haskell、Java 和 JavaScript 的库。

Sharemind MPC 在一个固定大小的环上实现了一个自定义的加法秘密共享方案。这些固定大小的整数的行为与传统的 C 语言整数一致，而且该框架包含一个浮点库。该协议是为确切的三个服务端编写的，但也支持任意多的参与方，在三个计算服务端之间秘密共享他们的输入到一个数据库结构。我们的示例用一个单一的客户端程序通过了所有的输入值。SecreC 语言具有很强的表现力，并在网上有很好的记录。它所支持的客户端库并没有那么好的文档。

Sharemind MPC 平台有几种许可方式。通过Cybernetica，我们使用的是学术服务。这个许可证使我们能够获得协议的实现。该平台还包括一个开源的模拟器，其中包括 SecreC 语言、其标准库和安全计算的模拟器。仿真器可以作为虚拟机和可编译的源代码使用。我们在这两个版本上都成功运行了我们的示例。仿真器不支持客户端代码，而且参数必须在命令行中传递。

作为学术许可的一部分，我们有机会接触到 Sharemind 的一些员工，他们在整个开发过程中提供了 "适当的帮助"，而且我们认为这是一个在线资源。

建议：Sharemind MPC 平台适用于各种不同的目的。我们推荐它给那些希望实现安全计算的公司，特别是对于大型或复杂的功能，以及那些需要 MPC 作为项目工具的学术界人士。

I. PICCO

PICCO[138], [137]是一个具有自定义秘密共享协议的通用编译器。它包括三个主要的软件贡献：一个编译器，它把 C 语言扩展转化为本地 C 语言用于安全计算；一个产生和重构秘密共享输入和输出的I/O工具；以及一个启动计算的工具。PICCO 在一个混合模型下执行计算，同时使用一个信息论的乘法协议 [70] 和用于其他操作的自定义原语。它支持任意数量的参与方，但需要诚实的大多数。

PICCO 允许在私有变量上设置条件，但是不允许公共变量被分配在私有变量的范围。它还允许在私有位置对数组进行索引，尽管这是以多路复用器的形式实现的，而不是以 ORAM 的形式。它支持指向私有数据的指针和动态内存分配标准的类 C 语言语法。该语言支持单比特的整数类型以近似布尔值，虽然我们运行了提供的例子，但我们无法使用它们成功地编写我们自己的程序。

这些语言在文件中得到了很好的记录。代码库中包括许多 C 语言扩展的例子，但没有包括编译和运行一个程序所需的额外文件的例子。编译和执行安全计算的过程是冗长的，但有很好的记录，同时还需要多个配置文件，和明确地生成和重建秘密共享的输入和输出值。

建议：PICCO 适合于开发者或需要真正多方实现的学术界。我们没有发现有意义的 issues，而且它允许在配置计算方面有很大的灵活性。

J. Frigate

Frigate[105]将一种新颖的类 C 语言编译成一种自定义的布尔电路，用于表示任意数值的输入。该框架强调使用良好的软件工程技术，包括一个广泛的测试套件，同时专注于模块化和可扩展性。电路格式最大限度地减少了文件的大小，并且该框架包括一个解释器，用于有效地连接生成的电路和其他应用程序。

Frigate 产生了一个回路，因此所有的操作默认情况下都是安全的。这个类型系统非常简单，只有三种本地类型：有符号和无符号整数以及结构体。虽然没有明确的布尔类型，但整数的大小是任意的，并且语言定义了比较和位操作符，所以它支持同样的功能。全局变量是不允许的。Frigate 允许数组，但它们必须包含在结构体中。电路编译器提供了有用的异常，并且源代码包括对解释器选项的简要描述和一个语言描述。

一个可用性问题是，基本的算术运算只对相同类型和大小的操作数进行了定义。这可能会增加某些应用的电路尺寸。该框架不包括一个模拟器，因此任何正确性检查需要一个单独的后端。为了测试 Frigate 生成的电路，我们编写了一个工具来将 Frigate 电路转换为适合在 BMR 协议[16]中执行的格式。

建议：Frigate 为快速生成电路提供了一种富有表现力的类 C 语言，是一个很好的方法来估计一个特定计算的电路大小。然而，即使有了我们的转换工具，将 Frigate 的电路形式连接到有用的后端，执行一个端到端 MPC 计算，需要用户采取相对繁琐的操作。

K. CBMC-GC

CBMC-GC [82], [64]从ANSI-C的子集产生布尔电路。它基于 CMBC[40]，一个有界模型检查器，该检查器将任何 C 语言程序翻译成布尔约束，然后调整该工具的输出以产生一个优化的电路用于安全多方计算。该编译器可以优化最小尺寸或最小深度的电路。它产生的电路适用于任何数量的输入方；我们编译并模拟了最多有十个参与方的样本程序。

我们没有找到足够的，关于 CMBC-GC 采用的 ANSI-C 子集所受到的限制的文档。例如，输入到主文件的变量名必须以 INPUT_ 为前缀。数组不能作为参数传递；它们必须被包裹在一个结构体中。非默认的整数类型，如特定宽度的整数，可以使用，但需要明确的包括在内。我们无法编译一个使用 C 布尔类型的程序。该框架包括一个基本的的浮点运算集，并允许对秘密数据进行条件判断。它有一些配置选项，如电路优化技术、展开循环的深度，以及最小化时间限制。

CBMC-GC 包括一个用 ABY（第 VI-F节）运行电路的工具。我们无法用这个转换器运行一个例子；似乎 CBMC-GC 的代码引用了一个已废弃的 ABY API。CBMC-GC 也包括一个工具来输出其他格式的电路，这包括由 TinyGarble 编译器使用的简单电路描述（SCD）；Fairplay 的安全硬件定义语言（SHDL）；以及 Bristol 电路格式[124]。我们用 TinyGarble 编译器（第VI-D节）测试了这个工具的输出，但无法运行任何例子。我们无法确定错误是因为 CBMC-GC 生成的电路还是由 TinyGarble 造成的。

建议：CBMC-GC 使用强大的工具来产生优化的电路，但是我们无法成功执行它所产生的任何电路。

VII. 讨论

A. 利用现有编译器相关的研究

虽然程序设计语言研究对编译器的创造有一定作用，但是MPC相关研究很少用到了这些技术。当然，Wysteria是一个显著的例外，但它距离实际应用有较大的工程空白需要填补。然而，如果框架研究对程序语言设计和验证采取更具有原则的方法，那么多方安全社区将会受益良多。

编译器的正确性是一个显著需要改进的领域。我们团队发现这些框架研究在逐步成功地阻止安全威胁过程中，许多框架存在正确性的问题。通过定义和实现类型的规则能够确保正确的输出，从而减少上述存在的正确性问题，然而这些框架研究常常忽略这一点。

B.文档资料

一般情况下，缺少可参考的文档材料是研究人员使用安全多方计算框架时最大的障碍。多方安全社区投入数千小时来实现本文中提到的这些框架，以及相关的文档资料使这些框架更加方便使用。

当使用类似这些安全多方计算框架的复杂软件系统时，各种形式和多种类型的文档资料对用户具有很大帮助的。我们的评估标准推荐了几种我们认为特别有用的文档类型，同时我们也鼓励安全多方计算相关项目开发人员和研究者为用户提供多种类型的资源以作参考。

除了这些作者提供的静态文档资料外，在线动态的资源也极有价值。这些资料包括归档的来往信件，如归档的邮件列表、Google论坛以及GitHub上的问题单等。这些资源能够减轻研究者的负担，使他们能够从反复询问相同问题的私人信件中解放出来。此外，样例程序以及社区不断丰富的简单样例程序仓库也是十分重要的资源，它们能够显著地提高这些安全多方计算框架的可用性和实用性。

C.标准化和基准

本篇论文中的大部分框架都是依据某个特定的特性进行设计，比如类型系统或某个优化的技术。将跨框架的通用的基本特性标准化的工作，能够使得研究者更加专注于在研框架的核心特性以及为用户提供一定程度的一致性。标准化还能为性能评估设定更为一致的基准。然而，对于即将过时的技术进行标准化是一个潜在的问题，例如，我们可以推荐一种电路的格式，但是这对于当前使用不同中间表示的混合框架而言，是没有任何意义的。

目前有如下几个项目正在推进安全多方计算领域标准化。SCAPI[1] [56]定义了一个通用的API，为安全计算中通用的密码学要素和原语提供了接口。它的目标是为密码学家实现安全多方计算提供统一、灵活、高效的标准库，此外，其还包括了一系列的重要文档资料。FRESCO[60] 定义了一系列用于功能描述、协议定义和评估的java API。作为一个展示，该项目包含几个示例项目的前端代码和带有MASCOT预处理的SPDZ协议实现。SCALE-MAMBA系统使用了一组字节码作为中间表示，这些字节码被其他项目重用，如Jana编译器[5]。

由于对处理能力、网络带宽、网络延迟、计算架构和框架结构的各种依赖性，跨框架性能基准存在较大的挑战。理论上的性能评估方法很难实际应用，并且框架在某个基准环境中表现较好，但是在另一个环境中可能表现很差。尽管如此，基准还是能够帮助人们洞察一个框架的优劣，而且如果不将基准作为框架贡献的唯一衡量标准，其还是具有价值的。此外，最近Barak等人[8]为具有兼容架构的框架之间的性能比较提供了相应的方法。

我们建议社区能够共同讨论研究能够表现框架能力的一系列一致性问题和关联指标，并且将它们作为框架之间性能比较的基准。标准化基准测试存在一些已知的问题：某些指标可能和所有的协议都不相关；编译器可能只会针对基准测试的问题进行性能优化而不是针对更加广泛的情况；章节V-E中提到的性能测试问题仍然存在。我们希望对基准测试进行仔细的设计能够缓和当前存在的这些问题，并且期望能够为将来的从业者提供有效的工具。