安全多方计算

安全多方计算（MPC）允许互不信任的各方共同计算其私有输入的函数，同时除了商定的输出之外不泄露任何信息。

Definition

安全多方计算是一种协议，它使一组各方（每方持有一个私有输入）能够计算一个商定的函数，从而使每方都能获得正确的输出，并且除了这些输出之外，不了解其他方的任何输入信息。

Scope

本主题涵盖安全计算协议：理想/真实模拟安全定义、姚氏双向乱码电路、基于秘密共享的多方协议（GMW、BGW）、半诚实安全与恶意安全之间的区别，以及门限密码学。它涉及私有集合交集和安全聚合等实际应用。它不包括通常用作子协议的零知识证明，以及提供在加密数据上进行计算的替代途径的全同态加密。

Core questions

• 各方如何在不让任何一方看到其他方输入的情况下，对组合数据进行计算？
• 理想/真实模拟范式对安全协议有什么要求？
• 乱码电路如何实现安全双向计算？
• 基于秘密共享的协议如何扩展到多方并容忍腐败？
• 半诚实安全和恶意安全保证之间有什么区别？

Key concepts

• 私有输入和联合输出
• 理想/真实模拟
• 乱码电路
• 不经意传输
• 秘密共享
• 半诚实与恶意对手
• 门限密码学
• 私有集合交集
• 诚实多数与不诚实多数

Key theories

理想/真实模拟安全

如果对手在真实协议中能够实现的一切，在理想世界中（由一个受信任方计算函数）也能实现，那么一个MPC协议就是安全的——这保证了针对所建模腐败的隐私和正确性。

乱码电路和秘密共享

姚氏乱码电路允许两方评估任何布尔电路，其中一方加密真值表，另一方不经意地解密；秘密共享方案将输入分配给各方，以便子集共同计算门，而无需重建秘密。

Mechanisms

在姚氏双向协议中，一方通过加密每个门的真值表来混淆布尔电路，另一方则使用通过不经意传输获得的密钥来评估它，只学习输出。在秘密共享方法（GMW、BGW、SPDZ）中，每个输入被分成份额并分发给各方；加法门在份额上进行本地计算，乘法门则使用交互，之后重建输出份额。恶意安全增加了零知识证明或认证份额以检测欺诈行为。

Clinical relevance

MPC正在从理论走向实际部署，以实现隐私保护协作：机构在组合数据集上计算聚合统计数据，而无需汇集原始数据（波士顿性别工资差距研究）；公司运行私有集合交集以进行联系人发现和广告衡量；门限签名保护加密货币托管和证书颁发机构密钥；安全聚合支持隐私保护机器学习。

Evidence & guidelines

MPC得到了成熟的开放框架（例如MP-SPDZ）的支持，并且越来越多地得到门限密码学标准工作（NIST的多方门限密码学项目）的支持。安全保证关键取决于假定的腐败模型（半诚实与恶意）和腐败阈值（诚实多数与不诚实多数），这些必须与部署的信任假设相匹配。

History

Andrew Yao在1982-1986年间引入了安全双向计算和乱码电路思想（百万富翁问题）。Goldreich、Micali和Wigderson（1987）将安全计算扩展到任意数量的参与方，BGW和CCD协议（1988）在诚实多数的情况下提供了信息理论安全性。数十年的效率改进（不经意传输扩展、SPDZ）使MPC在2010年代足够实用，可以进行实际部署。

Key figures

• Andrew Yao
• Oded Goldreich
• Silvio Micali
• Avi Wigderson
• Adi Shamir

Seminal works

• yao1982
• goldreich2004
• katz2020

Frequently asked questions

MPC与同态加密有何不同？

两者都对私有数据进行计算，但同态加密允许单个方对其无法读取的密文进行计算，而MPC则将计算分布在多个交互方之间，没有单个方能够看到输入。它们有时会结合使用。

“半诚实”与“恶意”安全意味着什么？

半诚实（诚实但好奇）安全假设各方遵循协议，但试图从他们所看到的信息中学习额外信息。恶意安全则额外保护协议免受任意偏离协议的各方的侵害，这更强但成本更高。