编程总结

具体有效的安全多方计算协议：调查和更多

安全的多方计算（MPC）允许一组当事人在他们的隐私输入上联合计算一个函数，并且除了函数的输出外什么都不透露。在过去的十年中，MPC 已经从一个纯粹的理论研究迅速转变成一个具有实际意义的对象，人们对实际应用的兴趣越来越大，如保护隐私的机器学习（PPML）。在本文中，我们全面调查了在不诚实多数和诚实多数情况下，具有半诚实和恶意安全的具体有效的 MPC 协议的现有工作。我们重点考虑有中止的安全概念，也就是说，腐败的一方可以阻止诚实的一方在收到输出后收到输出。我们提出了设计不同风格的 MPC 协议的基本和关键方法的高层次想法，以及 MPC 的关键构建模块。对于 MPC 的应用，我们比较了已知的建立在 MPC 上的 PPML 协议，并描述了最先进的 PPML 协议的私有推理和训练的效率。此外，我们总结了几个挑战和开放性问题，以突破 MPC 协议的效率，以及一些有趣的未来工作，值得被解决。这项调查的目的是向那些对了解、改进和应用具体的高效 MPC 协议感兴趣的研究人员提供 MPC 的最新发展和关键方法。

基于 PaXoS 的 PSI：快速、恶意的隐私集合交集

我们提出了一个 2 方隐私集合相交（PSI）协议，它提供了针对恶意参与者的安全性，但几乎与 Kolesnikov 等人（CCS 2016）已知的最快的半诚实 PSI 协议一样快。

我们的协议是基于一种新的两方 PSI 方法，它可以被实例化以提供针对恶意或半诚实对手的安全性。该协议的独特之处在于，半诚实和恶意版本之间的唯一区别是对线性纠错代码的不同参数进行实例化。它也是第一个具体有效的 PSI 协议，同时具有线性通信和对恶意对手的安全性，同时在混合 OT 模型中运行（假设是一个不可编程的随机神谕）。

最先进的半诚实 PSI 协议利用了布谷鸟散列的优势，但事实证明，使用布谷鸟散列来实现恶意安全是一个挑战。我们的协议是第一个将布谷鸟散列法用于恶意安全的 PSI。我们通过一个新的数据结构来实现这一点，该结构被称为字符串的探测和 XOR（PaXoS），这可能是独立的兴趣。这个抽象结构抓住了以前数据结构的重要特性，最明显的是乱码布鲁姆过滤器。虽然乱码布隆过滤器的编码比原始数据大了 ，但我们描述了一种基于布谷鸟散列的显著改进的 PaXoS，它实现了恒定的速率，同时在其他相关的效率措施方面也不差。

不经意键值存储和放大的隐私集合交集

许多最近的隐私集合交集（PSI）协议将输入集编码为多项式。我们考虑更普遍的不经意键值存储（OKVS）的概念，它是一个数据结构，紧凑地表示所需的映射 。当 值是随机的，OKVS 数据结构隐藏了用于生成它的 值。最简单的（和大小最优的）OKVS 是一个多项式 ，它是用插值法选择的，这样 。

我们开始了对不经意键值存储的正式研究，并展示了导致迄今为止最快的 OKVS 的新构造。

与布谷鸟散列类似，目前的分析技术不足以找到具体的参数来保证我们的 OKVS 结构的小故障概率。此外，运行实验来验证一个小的故障概率上限的成本太高了。因此，我们展示了新的技术，将一个具有故障概率 的 OKVS 结构放大到具有类似开销和故障概率 的 OKVS。将 设置为适度的小，可以通过运行相对较少的 实验来验证它。这就验证了放大的 OKVS 的失败概率为 。

最后，我们描述了 OKVS 如何显著改善 PSI 的所有变体的技术水平。这导致了迄今为止最快的两方 PSI 协议，无论是在半诚实还是恶意的情况下。具体来说，在具有中等带宽的网络中（例如，30-300Mbps），我们的恶意双方 PSI 协议的通信量减少了 40%，比以前的最先进的协议快 20-40%，尽管后者只有启发式的信心。

VOLE-PSI：来自向量不经意线性评估的快速 OPRF 和电路 PSI

在这项工作中，我们提出了一种基于 VOLE 和 PaXoS 数据结构的批量化不经意伪随机函数（OPRF）的新构造。然后，我们将其用于标准转换，以实现来自 OPRF 的隐私集合交集（PSI）。我们的整体构造是非常高效的，具有 的通信和计算能力。我们证明，与半诚实的变体相比，我们的协议可以在实际上没有开销的情况下实现恶意的安全。对于输入大小 ，我们的恶意协议需要 6.2 秒和不到 59MB 的通信。这相当于每个元素低于 比特，这是迄今为止公布的任何 PSI 协议（半诚实或恶意）的最低数字。此外，在理论上，我们的半诚实（或恶意）协议可以实现低至 （或 ）比特对于 的元素，在 元素上内插一个多项式的额外成本。作为第二个贡献，我们提出了一个扩展，即 PSI 的输出在双方之间是秘密共享的。这种函数通常被称为电路 PSI。它允许双方在秘密共享的输出上执行后续的 MPC 协议，例如，训练一个机器学习模型。我们的电路 PSI 协议建立在我们的 OPRF 构造以及 PaXoS 数据结构的另一个应用之上。我们的协议实现了半诚实的安全性，并允许高效的实现，比以前的工作快 3 倍。

签署合同的随机性协议

提出了签署合同、认证邮件和掷硬币的随机协议。这些协议使用了一个 1-out-of-2 的不经意传输子协议，该协议是公理上定义的。

1-out-of-2 不经意传输允许一方在两个可识别的秘密中准确地传输一个秘密给他的对应方。第一个（第二个）秘密以一半的概率被接收，而发送方不知道收到的是哪个秘密。

我们提出了一个使用任何公钥密码系统的 1-out-of-2 不经意式传输的实现。

高效的批量不经意伪随机函数与隐私集合求交集的应用

我们描述了一种在半诚实对手存在的情况下对伪随机函数进行不经意评估（OPRF）的轻量级协议。在 OPRF 协议中，接收方有一个输入 ；发送方得到输出 ，接收方得到输出 ，其中 是一个伪随机函数， 是一个随机种子。我们的协议使用了 选 的 OT 扩展协议的新颖改编，当用于生成大批量的 OPRF 实例时，特别有效。实现 个 OPRF 实例的成本大约是实现 个标准 选 OT 实例的成本（使用最先进的 OT 扩展）。

我们详细探讨了我们的协议在半诚实安全隐私集合求交集（PSI）中的应用。最快的最先进的 PSI 协议（Pinkas 等人，Usenix 2015）是基于高效的 OT 扩展。我们观察到，我们的 OPRF 可以用来消除他们的 PSI 协议对各方项目的比特长度的依赖。我们实现了这两个 PSI 协议变体，发现对于 位字符串和足够大的集合的 PSI，我们的比 Pinkas 等人快 3.1 到 3.6 倍。具体来说，我们的协议只需要 3.8 秒就能安全地计算出大小为 集合的交集，而不考虑项目的比特长度。对于非常大的集合，我们的协议只比 PSI 的不安全的朴素散列方法慢 4.3 倍。

非交互式和信息论的安全可验证的秘密共享

它显示了如何将一个秘密分配给 人，使每个人都能验证他收到了关于该秘密的正确信息，而无需与其他人交谈。这些人中的任何一个人后来都可以找到这个秘密（ ），而少于 的人则得不到关于这个秘密的（香农）信息。该方案的信息率为 ，分配和验证每比特的秘密大约需要 个模块化乘法。它还显示了一些人如何在 "井" 中选择一个秘密并在他们之间可核查地分配它。

离散对数的一般声明的证明系统

离散对数知识的证明系统是密码学的一个重要基础。我们确定了基本的基础技术，概括了这些技术以证明离散对数之间的线性关系，并提出了一个描述离散对数知识的复杂和一般声明的符号。这个符号直接导致了一种构建高效的知识证明系统的方法。

部分同态加密的多方计算

我们提出了一个通用的多方计算协议，以防止主动对手破坏多达 个用户。该协议可用于安全地计算任何有限域 上的算术电路。我们的协议由一个预处理阶段和一个更有效的在线阶段组成，前者与要计算的函数和输入无关，后者是实际计算的地方。在线阶段是无条件安全的，总的计算（和通信）复杂度是 的线性，即用户的数量，而早期的工作是 的平方。此外，每个用户所做的工作只比在明处计算电路所需的工作大一个小常数。我们表明这对大领域的计算来说是最佳的。在实践中，对于 个用户，一个安全的 位乘法可以在 毫秒内完成。我们的预处理是基于一个有点同构的密码系统。我们扩展了 Brakerski 等人的方案，因此我们可以执行分布式解密，并在一个密文中并行处理许多值。我们的预处理阶段的计算复杂度由公钥操作主导，我们需要 次安全乘法操作，其中 是一个参数，随着密码系统的安全参数而增加。这个模型的早期工作需要 操作。在实践中，预处理为 个用户准备了一个安全的 位乘法，大约需要 毫秒。

为多数不诚实提供实用的隐蔽安全的 MPC— 或称：打破 SPDZ 的限制

（发音为 "Speedz"）是 Damg ̊ ard 等人在 Crypto 2012 中提出的 MPC 协议的昵称。在本文中，我们既解决了 的一些开放性问题，又对该协议进行了一些理论和实践上的改进。详细来说，我们首先设计并实现了一个隐蔽安全的密钥生成协议，以获得 公钥和共享的相关秘钥。然后，我们构建了一个隐蔽的和主动的安全预处理阶段，这两个阶段在效率和可证明的安全性方面都比以前的工作要好。

我们还建立了一个新的在线阶段，解决了 协议的一个主要问题：即在这项工作之前，预处理的数据只能用于一个函数的评估，然后必须为下一个评估从头开始重新计算，而我们的在线阶段可以支持反应性的功能。这一改进主要来自于我们的结构不需要参与者透露 密钥来检查 值的正确性。

MP-SPDZ：一个多功能的多方计算框架

多协议 （ ）是 （Keller 等人，CCS '13）的分叉， 是多方安全计算（MPC）协议的一个实现（Damgård 等人，Crypto '12）。 将 扩展到 个 MPC 协议变体，所有这些都可以用基于 Python 的相同的高级编程接口来使用。这大大简化了对不同协议和安全模型的成本比较。

这些协议涵盖了所有常用的安全模型（诚实 / 不诚实的多数和半诚实 / 恶意的腐败），以及二进制和算术电路的计算（后者是对素数和 的幂的调制）。采用的基本原理包括秘密共享、不经意传输、同态加密和混淆电路。

所实施的协议的广度加上一个可访问的高级接口，使得它适合于为具有或不具有安全计算背景的研究人员在各种安全模型中的计算成本进行基准测试。

本文旨在概述在 MP-SPDZ 开发过程中实现的各种协议和设计选择，以及编程接口的能力。

SIMC：以半诚实的安全成本防范恶意客户的 ML 推理

安全推理允许模型所有者（或称服务器）和输入所有者（或称客户端）对机器学习模型进行推理，而不向对方透露其私人信息。大量的工作显示了通过安全的 2 方计算来解决这个问题的有效加密方案。然而，他们假设双方都是半诚实的，即遵循协议规范。最近，Lehmkuhl 等人表明，恶意的客户可以使用新的模式提取攻击来提取服务器的整个模型。为了补救这种情况，他们引入了客户端 - 恶意威胁模型，并建立了一个安全推理系统 MUSE，即使在客户端是恶意的情况下，也能提供安全保证。

在这项工作中，我们设计并建立了 SIMC，一个新的加密系统，用于客户端恶意威胁模型中的安全推理。在 MUSE 考虑的安全推理基准上，SIMC 的通信量减少了 23-29 倍，比 MUSE 快 11.4 倍。SIMC 使用非线性激活函数（如 ReLU）的新型协议获得了这些改进，其通信量比 MUSE 少 28 倍以上，性能比 MUSE 高 43 倍。事实上，SIMC 的性能击败了最先进的半诚实安全推理系统

最后，与 MUSE 类似，我们展示了如何将 SIMC 的大部分加密成本推到一个独立于输入的预处理阶段。虽然这个协议的在线阶段的成本，即 SIMC++，与 MUSE 相同，但 SIMC 的整体改进转化为对 MUSE 预处理阶段的类似改进。

Paillier 的概率性公钥系统的概括、简化和一些应用

我们提出了对 Paillier 的概率公钥系统的概括，在这个系统中，扩展因子被降低，即使在公钥被固定后，也可以调整方案的块长，而不会失去同态特性。我们表明，这个概括与 Paillier 的原始系统一样安全。我们构建了一个广义方案的阈值变体，以及零知识协议，以表明一个给定的密码文本加密了一组给定的明文中的一个，以及验证明文的乘法关系的协议。

然后，我们展示了这些构件如何用于将该方案应用于高效的电子投票。与之前最知名的方案相比，这大大减少了计算选举的最终结果所需的工作。我们展示了是否投票的基本方案如何可以很容易地适应于为 个候选人中的 个候选人投票。在适当的物理假设下，同样的基本构件也可以用来提供无收据的选举。 选 的方案可以被优化，在一定的参数值范围内，选票的大小只有 比特。

通过加法同态加密保护隐私的深度学习

我们提出了一个保护隐私的深度学习系统，在这个系统中，许多学习参与者对所有的组合数据集进行基于神经网络的深度学习，而不向中央服务器透露参与者的本地数据。为此，我们重新审视了 Shokri 和 Shmatikov（ACM CCS 2015）以前的工作，并表明，用他们的方法，本地数据信息可能会泄露给一个诚实但好奇的服务器。然后，我们通过建立一个具有以下特性的增强系统来解决这个问题。1）没有信息被泄露给服务器，2）与普通的深度学习系统相比，在组合数据集上的准确性保持不变。我们的系统连接了深度学习和密码学：我们利用应用于神经网络的异步随机梯度下降法，并结合加法同态加密法。我们表明，我们对加密的使用给普通的深度学习系统增加了可容忍的开销。

使用同态加密和可验证计算的安全联邦学习框架

在本文中，我们提出了第一个联邦学习（FL）框架，该框架在所产生的模型不被披露给聚合服务器的情况下，可以安全地抵御来自聚合服务器的保密性和完整性威胁。我们通过结合同态加密（HE）和可验证计算（VC）技术来做到这一点，以便在加密域中直接执行联合平均运算（通过 HE），并产生运算正确应用的正式证明（通过 VC）。由于聚合函数的简单性，我们能够将我们的方法建立在加法 HE 技术上，这些技术在安全方面非常成熟，而且效率很高。我们还引入了一些优化措施，使我们能够在更大的深度学习模型的末端达到实际的执行性能。本文还在 FEMNIST 数据集上提供了广泛的实验结果，证明该方法以实际意义上的计算和通信开销为代价，保留了所产生的模型的质量，至少在客户和服务器端都可以涉及高端机器的跨语境设置上是如此。

来自改进的 OKVS 和 VOLE 子域的极速 PSI

我们提出了新的半诚实和恶意安全的 PSI 协议，这些协议在通信和运行时间上都比之前的所有作品要好几倍。例如，我们对 的半诚实协议可以在 0.37 秒内完成，而之前最好的是 2 秒（Kolesnikov 等人，CCS 2016）。在 4 个线程的情况下，这可以进一步减少到 0.16 秒，速度提高了 12 倍。同样，我们的协议发送 比特，而下一个通信效率最高的协议是 比特（Rindal 等人，Eurocrypt 2021）。此外，我们将我们的新技术应用于 Rindal 等人的电路 PSI 协议，运行时间提高了 6 倍。这些性能结果是通过两种类型的改进获得的。

首先是对 Rindal 等人的协议进行了优化，利用子域向量不经意线性评估。这一优化使我们的结构首次实现了 的通信复杂性，其中 是统计安全参数。特别是，我们的协议的通信开销不随计算安全参数乘以 而扩展。

我们的第二个改进是对 OKVS 数据结构的改进，我们的协议主要依赖于这个结构。特别是，与之前的工作相比，我们的结构提高了计算和通信效率（Garimella 等人，Crypto 2021）。这些改进源于对数据结构的算法改变，以及获得其失败概率的渐进和严格的具体界限的新技术。这反过来又允许高度优化的参数选择，从而提高性能。

具有基数的隐私交集求和的两方恶意安全

具有基数的（cardinality）隐私交集求和允许两方，其中每方持有一个隐私集合，其中一方还持有与它的集合中的每个元素相关的隐私整数值，共同计算两个集合的相交的基数，以及相交中所有元素的相关整数值的总和，除此之外没有其他。

我们提出了一种新的隐私交集求和的构造，它提供了带有中止功能的恶意安全，并保证双方在成功完成协议后都能收到输出。我们构造的一个核心构件是一个称为洗牌分布式不经意伪随机函数（DOPRF）的基元，它是一个伪随机函数（PRF），使用双方共享的密匙提供不经意评估，此外还允许不经意地混合几个平行不经意评估的 PRF 输出。我们提出了第一个具有恶意安全的洗牌 DOPRF 的构造。我们进一步提出了几个新的 sigma 证明协议，用于跨 Pedersen 承诺、ElGamal 加密和 Camenisch-Shoup 加密的关系，我们在主要构造中使用了这些协议，为此我们开发了新的批处理技术以减少通信。

我们实现并评估了我们协议的效率，并表明我们可以实现通信成本只比最有效的半诚实协议大 4-5 倍。当测量在云中执行协议的货币成本时，我们的协议比半诚实协议的成本高 25 倍。我们的结构还允许不同的参数制度，使通信和计算之间的权衡成为可能。

更有效的，对恶意对手有安全保障的 OT 扩展

不经意传输（OT）是密码学中最基本的基元之一，被广泛用于安全的双方和多方计算的协议中。随着安全计算变得更加实用，对实用的大规模不经意传输协议的需求也变得更加明显。不经意传输扩展是使相对较少的 "基础 OT" 能够以较低的成本被用来计算非常多的 OT 的协议。在半诚实的情况下，Ishai 等人（CRYPTO 2003）提出了一个 OT 扩展协议，其中每个 OT（基于基础 OT）的成本只是几个哈希函数操作。在恶意设置中，Nielsen 等人（CRYPTO 2012）提出了一个有效的主动对手设置的 OT 扩展协议，在随机预言机模型中是安全的。

在这项工作中，我们提出了一个针对恶意对手设置的 OT 扩展协议，该协议比以前的工作更有效，使用的通信更少。此外，我们的协议可以被证明在随机预言机模型和标准模型中都是安全的，并具有一定的相关性稳健性。鉴于 OT 在许多安全计算协议中的重要性，提高 OT 扩展的效率是使安全计算实用化的另一个重要步骤。

以减少计算和通信的方式从同态加密中获得标记的 PSI

众所周知，完全同态加密（FHE）可用于在不平衡设置中建立高效的（标记的）隐私集合求交协议，其中一个集比另一个大得多（Chen 等人（CCS'17，CCS'18））。在本文中，我们展示了对这些工作的多种算法改进。特别是，我们的协议有一个渐进的更好的计算成本，只需要 同态乘法，并且通信复杂度在较大的集合大小 中是亚线性的。

我们证明我们的协议在许多实际参数上明显优于 Chen 等人（CCS'18）的协议，特别是在在线通信成本方面。例如，当相交于 和 个项目集时，我们的协议减少了 71% 以上的在线计算时间和 63% 以上的通信。当相交于 个和 个项目集时，我们的协议将在线计算时间减少 27%，通信减少 63%。我们与其他最先进的不平衡 PSI 协议的比较表明，当 时，我们的协议具有最佳的总通信复杂度。对于有标签的 PSI，我们的协议也优于 Chen 等人（CCS'18）。当相交于 和 个项目集时，较大的项目集有相关的 字节的标签，我们的协议将在线计算时间减少 67% 以上，通信减少 34%。

最后，我们展示了一种修改，在更大的集合规模 下，通信成本几乎不变，但在今天的 CPU 上计算复杂度高得不切实际。例如，要使一个 项的集合与 、 或 大小的集合相交，我们的概念验证实现只需要 0.76MB 的在线通信，这比 Chen 等人（CCS'18）的改进超过了 24 倍。

高效的隐私匹配和集合交集

我们考虑计算两方隐私数据集的交集问题，其中数据集包含来自大领域的元素列表。这个问题在在线协作方面有很多应用。我们提出了基于使用同态加密和平衡散列的协议，适用于半诚实和恶意的环境。对于长度为 k 的列表，我们得到了 通信开销和 计算。半诚实环境的协议在标准模型中是安全的，而恶意环境的协议在随机预言机模型中是安全的。我们还考虑了近似交点大小的问题，显示了解决这个问题的通信开销的线性下限，并提供了一个合适的安全协议。最后，我们研究了匹配问题的其他变体，包括将协议扩展到多方设置，以及考虑近似匹配的问题。