安全多方计算获分布式计算最高荣誉

安全多方计算获分布式计算最高荣誉

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

2023年，计算机协会分布式计算领域的Dijkstra奖授予了三篇关于安全MPC的论文，其中一篇《可验证秘密共享与诚实多数的多方协议》源于某中心密码学团队高级首席科学家Tal Rabin的博士论文。

信息论安全突破

安全MPC领域始于1982年，当时Andrew Yao发表了关于安全两方计算的论文。然而Yao的MPC方案安全性依赖于大整数分解的难度。这立即引发了一个问题：即使在对手拥有无限计算资源的情况下，安全MPC是否仍然可能？

2023年获得Dijkstra奖的三篇论文都解决了信息论安全MPC的问题。前两篇论文证明，如果计算中不超过三分之一的参与者是恶意行为者，信息论安全MPC是可能的。

Tal Rabin与Michael Ben-Or的论文将这一比例提高到约二分之一，这在信息论设置中是可证明的最大叛徒容忍数，也是Yao在其原始计算有界方法中证明的阈值。

信息检查机制

Rabin和Ben-Or论文的核心是将数字签名概念适配到信息论设置中。他们提出了一种称为“信息检查”的方法，虽然不如数字签名强大，但不对叛徒的计算限制做任何假设。

该协议涉及分发者、中介和接收者。为模仿数字签名的安全保证，信息检查必须满足两个标准：

1. 如果分发者和接收者是诚实的，接收者将始终接受合法的s，并以高概率拒绝任何欺诈性替换
2. 无论分发者是否诚实，中介都能以高概率预测接收者是否会接受s

零知识证明应用

为满足第二个标准，Rabin和Ben-Or使用了零知识证明机制。分发者不是将算术操作应用于s和单组随机生成数字，而是将其应用于s和多组随机生成数字，产生多个(bi, ci)对。

在分发者将这些对发送给接收者后，中介随机选择其中一半并要求接收者披露它们。由于中介知道s，它可以确定算术关系是否成立，从而判断分发者是否向接收者发送了有效的(bi, ci)对。

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

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

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

在Rabin和Ben-Or的协议中，发送给所有接收者的所有(bi, ci)对都是使用相同的多项式函数生成的。作者通过零知识证明机制，使分发者能够证明所有接收到的对都符合多项式，而不披露多项式本身。

这项35年前的研究为当今的安全MPC协议设计奠定了理论基础，特别是在后量子密码学时代，信息论密码方法变得愈发重要。