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

某机构Tal Rabin荣获分布式计算领域Dijkstra奖该奖项旨在表彰某机构首席首席科学家、宾夕法尼亚大学教授提出的一项协议该协议实现了信息论安全多方计算的理论极限。作者Larry Hardesty2024年2月8日6分钟阅读安全多方计算简介安全多方计算MPC是一种计算范式允许多个参与方共同计算一个聚合函数例如计算他们的平均工资而无需向彼此透露任何私人信息例如各自的工资。该技术已广泛应用于拍卖设计、密码学、数据分析、数字钱包安全以及区块链计算等领域。Tal Rabin是某机构云计算部门密码学组的高级首席科学家也是宾夕法尼亚大学计算机科学教授同时也是国际计算机学会ACM2023年分布式计算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并将其传递给中介中介随后可能会在某个时间将其传递给接收者。为了模拟数字签名的安全保障信息检查必须满足两个标准如果分发者和接收者是诚实的接收者将始终接受合法的s并且将以高概率拒绝任何欺诈性替换。无论分发者是否诚实中介都可以高概率地预测接收者是否会接受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更多精彩内容 请关注我的个人公众号 公众号办公AI智能小助手或者 我的个人博客 https://blog.qife122.com/对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号网络安全技术点滴分享