信息论安全多方计算协议突破

某机构Tal Rabin荣获分布式计算领域Dijkstra奖

该奖项旨在表彰某机构首席首席科学家、宾夕法尼亚大学教授提出的一项协议，该协议实现了信息论安全多方计算的理论极限。

作者：Larry Hardesty

2024年2月8日

6分钟阅读

安全多方计算简介

安全多方计算（MPC）是一种计算范式，允许多个参与方共同计算一个聚合函数（例如计算他们的平均工资），而无需向彼此透露任何私人信息（例如各自的工资）。该技术已广泛应用于拍卖设计、密码学、数据分析、数字钱包安全以及区块链计算等领域。

Tal Rabin是某机构云计算部门密码学组的高级首席科学家，也是宾夕法尼亚大学计算机科学教授，同时也是国际计算机学会（ACM）2023年分布式计算Dijkstra奖的获奖者之一。

2023年，ACM的年度Dijkstra分布式计算奖授予了20世纪80年代末关于安全MPC的三篇论文。其中一篇题为《具有诚实多数的可验证秘密共享与多方协议》的论文，源于Tal Rabin的博士论文。她的导师Michael Ben-Or（耶路撒冷希伯来大学计算机科学教授）是该论文的合著者。

有趣的是，Tal Rabin的父亲Michael Rabin也曾于2015年获得Dijkstra奖，这使得他们成为唯一一对获得该奖项的父子。更值得注意的是，Michael Rabin的获奖合作者正是他的博士生Michael Ben-Or。“所以我是我父亲的学术孙子，”Rabin说道。

信息论安全

安全MPC领域始于1982年，当时姚期智（现清华大学计算机科学教授）发表了关于安全两方计算的论文。然而，姚期智方案的安全性依赖于大整数因式分解的难度——这与当今确保大多数在线金融交易安全的计算假设相同。姚期智的结果立即提出了一个问题：即使对手拥有无限的计算资源（即信息论安全设定，而非计算安全设定），安全MPC是否仍然可能？

2023年Dijkstra奖的三篇获奖论文都解决了信息论安全MPC的问题。前两篇论文均发表于1988年ACM计算理论研讨会（STOC），证明如果计算中不超过三分之一的参与者是暗中共享信息并串通操纵结果的恶意行为者，则信息论安全MPC是可行的。

Tal Rabin和Michael Ben-Or的论文于次年发表在STOC上，将该比例提高到（大约）二分之一，这在信息论设定中被证明是可容忍的背叛者数量的理论最大值。这也是姚期智为其原始计算有界方法证明的阈值。

在Rabin和Ben-Or论文发表35年后的今天，信息论安全MPC技术开始找到应用。随着能够高效分解大数的通用量子计算机逐渐成为现实，信息论安全（而非计算安全）密码学方法变得更加紧迫。“我们团队的目标是应用MPC技术来提高某机构的安全性和隐私性，”Rabin说。

信息检查

Rabin和Ben-Or论文的核心是将数字签名的概念适应到信息论设定中。数字签名是公钥密码学的一种应用：文档的创建者拥有一个私有的签名密钥和一个公开的验证密钥，两者都来源于一个非常大的数的质因数。计算文档签名需要私钥，但验证签名只需要公钥。而对手无法在不计算出该数的因数的情况下伪造签名。

Rabin和Ben-Or提出了一种称为信息检查的方法，该方法虽然不如数字签名强大，但不假设背叛者有计算限制。事实证明，它是安全多方计算的充分基础。

Rabin和Ben-Or的协议涉及一个分发者、一个中介和一个接收者。分发者拥有某个数据项s，并将其传递给中介，中介随后可能会在某个时间将其传递给接收者。

为了模拟数字签名的安全保障，信息检查必须满足两个标准：

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

这两个标准共同确立了如果分发者或中介（但不能两者同时）不诚实，则可以检测到欺诈性替换。

为了满足第一个标准，分发者向中介发送两个值：s和另一个数字y。它向接收者发送一个不同的随机数对(b, c)，这些数满足一个算术运算（例如，y = bs + c）。中介知道y和s，但不知道c或b；如果它试图向接收者传递一个假的s，算术运算将会失败。

零知识证明

为了满足第二个标准，Rabin和Ben-Or使用了零知识证明，这种机制使一方能够证明自己知道某个值而无需透露该值本身。分发者不对s和一组随机生成的数字应用算术运算，而是对s和多组随机生成的数字应用该运算，产生多个(bi, ci)对。在分发者将这些对发送给接收者后，中介随机选择其中一半，并要求接收者披露它们。

由于中介知道s，它可以确定算术关系是否成立，从而确定分发者是否向接收者发送了有效的(bi, ci)对。另一方面，由于中介不知道未披露的对，如果它是不诚实的，它就无法通过尝试向接收者传递假的y和假的s来欺骗系统。

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

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

然而，为安全MPC提供基础需要更强的可验证秘密共享标准，这意味着无论干扰如何，接收者的集体重建都将成功。Rabin和Ben-Or论文的第二个主要贡献是一种利用弱秘密共享实现可验证秘密共享的方法。

在Rabin和Ben-Or的协议中，发送给所有接收者的所有(bi, ci)对都是使用相同的多项式函数生成的。在多接收者设定中，多项式的次数（其最大指数）是接收者数量的一半。为了证明秘密已被正确共享，分发者需要证明所有接收到的对都符合该多项式——而无需披露多项式本身。该机制再次使用了零知识证明。

“我们希望各方通过弱秘密共享承诺他们的值，”Rabin解释说。“所以现在你知道它要么是一个值，要么什么都没有。然后分发者针对这些值证明它们都位于T次多项式上。一旦证明完成，你就知道通过弱秘密共享的值要么被打开，要么不被打开。你知道所有被打开的值都在同一个T次多项式上。现在你知道你可以重建了。”

当Rabin和Ben-Or发表他们的论文时，MPC研究还处于起步阶段。“今天，你可以做得更好、更高效，”Rabin说。但论文的核心成果是理论性的。如今，安全MPC协议的设计者可以使用他们选择的任何证明机制，并且他们将享受到35年前Rabin和Ben-Or确立的相同的可计算性和容错保证。

研究领域

• 安全、隐私与滥用预防

标签

• 后量子密码学
• 可证明安全性
• 奖项与荣誉FINISHED