分布式计算安全协议获迪杰斯特拉奖

安全多方计算（MPC）是一种计算范式，允许多方在不泄露任何私人信息的情况下计算聚合函数（例如平均工资）。该技术已应用于拍卖设计、密码学、数据分析、数字钱包安全和区块链计算等领域。

2023年，计算机协会年度迪杰斯特拉分布式计算奖授予了三篇关于安全MPC的论文，这些论文均发表于1980年代末。其中一篇论文《可验证秘密共享与诚实多数的多方协议》源于某中心密码学组高级首席科学家Tal Rabin的博士论文。该论文由Rabin及其导师Michael Ben-Or共同完成。

值得注意的是，Rabin的父亲Michael Rabin也曾于2015年获得迪杰斯特拉奖，这使得Rabin父子成为该奖项唯一的父子得主。更值得一提的是，Michael Rabin的共同获奖者之一正是他的博士生Michael Ben-Or。Rabin表示：“因此，我是我父亲的学术孙辈。”

信息论安全

安全MPC领域始于1982年，当时Andrew Yao发表了一篇关于安全两方计算的论文。然而，Yao的MPC方案的安全性依赖于大整数分解的难度。Yao的结果立即引发了一个问题：即使对手拥有无限计算资源，安全MPC是否仍然可能？这种设置被称为信息论（与计算相对）安全设置。

2023年迪杰斯特拉奖的三篇获奖论文都解决了信息论安全MPC的问题。前两篇论文证明，如果计算中不超过三分之一的参与者是恶意行为者，信息论安全MPC是可能的。Tal Rabin和Michael Ben-Or的论文将这一比例提高到（约）二分之一，这被证明是信息论设置中可以容忍的叛徒最大数量。

信息检查

Rabin和Ben-Or论文的核心是将数字签名的概念适应到信息论设置。他们提出了一种称为"信息检查"的方法，该方法不如数字签名强大，但不假设叛徒的计算限制。事实证明，这足以作为安全多方计算的基础。

他们的协议涉及经销商、中介和接收方。经销商有一个数据项s，将其传递给中介，中介可能在稍后时间将其传递给接收方。为了模拟数字签名的安全保证，信息检查必须满足两个标准。

零知识证明

为了满足第二个标准，Rabin和Ben-Or使用了零知识证明，这是一种使一方能够证明它知道某个值而不披露该值本身的机制。经销商不是将算术操作应用于s和一组随机生成的数字，而是将其应用于s和多组随机生成的数字，产生多个(bi, ci)对。

从弱秘密共享到可验证秘密共享

接下来，Rabin和Ben-Or将这一结果推广到有多个接收者的情况，每个接收者接收自己的si。作者表明，他们的协议支持弱秘密共享，这意味着如果接收者试图从各自的si中集体重建一个值，要么他们将重建正确的值，要么计算将失败。

然而，为安全MPC提供基础需要更强的可验证秘密共享标准。Rabin和Ben-Or论文的第二个主要贡献是利用弱秘密共享实现可验证秘密共享的方法。

当Rabin和Ben-Or发表论文时，MPC研究还处于起步阶段。Rabin表示：“今天，你可以更好、更高效地进行信息检查。“但论文的核心结果是理论性的。今天，安全MPC协议的设计者可以使用他们选择的任何证明机制，并且他们将享受与Rabin和Ben-Or在35年前建立的相同的可计算性和叛徒容忍度保证。