近日，清华大学助理教授宋一凡在异步网络模型中提出了一种新的基于秘密分享的无条件多方安全计算协议，首次实现每个电路门的开销为与参与方数量成线性关系的通讯量以及进行常数次秘密分享。同时，团队给出了首个线性复杂度的秘密分享机制。将两者结合，团队首次实现了在异步网络下通讯复杂度与参与方数量成线性关系的多方安全计算协议。对分布式系统和多方安全计算方向具有重要价值。相关2项成果收录在Crypto 2024，合作者中计小宇和李君儒为交叉信息院博士生。
01 论文详情
多方安全计算允许互不信任的若干个参与方利用各自的隐私数据完成一个共同的计算任务，Ben-Or、Canetti、Goldreich [STOC’ 93]和Ben-Or、Kelmer、Rabin [PODC’ 94]最早奠基了多方安全计算协议在异步网络下的可行性。在这之后，尽管有很多工作在提升协议的通讯效率，目前在无条件安全以及最优恶意参与方数量的情况下取得的最好结果对于每个电路门的通讯量仍与参与方数量的四次方成正比，与之相对的，在同步网络模型下，最好结果对于每个电路门的通讯量仅与参与方数量呈线性关系。
宋一凡团队在异步网络模型下提出了一种新的基于秘密分享的无条件安全的多方安全计算协议，这个协议对于每个电路门的开销为与参与方数量成线性关系的通讯量以及进行常数次秘密分享，在此之前，最好的工作[IEEE Trans. Inf. Theory’ 17]需要参与方数量平方关系的通讯量以及进行参与方数量成线性关系次的秘密分享。在上述成果基础上，团队在异步网络下给出首个线性复杂度的秘密分享机制，在此之前，最好的工作[J.Crypto’ 23]需要参与方数量立方关系的通讯量。将两个成果相结合，团队给出了首个在异步网络下通讯复杂度与参与方数量成线性关系的多方安全计算协议，这与已知的同步网络模型下的多方安全协议的通讯复杂度相当。这项工作为在不依赖同步时钟和网络延迟的环境下实现高效、安全的多方计算提供了可能，在理论上和实践上都具有重要意义。
技术上讲，异步网络模型的主要困难在于保证协议能够顺利运行并终止（Liveness），造成这个困难的原因是当一个参与方没有接收到另一个参与方的信息时，我们无法判断是由于网络延迟造成信息尚未送达还是恶意参与方拒绝参与协议。为了避免因恶意参与方拒绝参与协议而导致协议无限等待，参与方只能期待接收诚实参与方数量的信息后就继续执行；但另一方面，未接收到的信息可能是因为网络延迟造成，而接收到的一部分信息反而来自恶意参与方，这使得异步网络模型下的协议对于恶意参与方数量的容忍度要低于同步网络下的协议，同时也为协议的构造带来巨大的障碍。为了克服这个困难，宋一凡团队提出两个更加高效但均无法保证终止的协议，其中第一个协议的终止需要有足够多的恶意参与方参与，而第二个协议的终止需要有足够少的恶意参与方参与，通过将两个协议巧妙地联系在一起，每个参与方需要先参加第一个协议才能参加第二个协议，这使得无论攻击者的策略如何，至少有一个协议的终止条件得到满足。
宋一凡团队提出的异步网络下构建具有线性复杂度的多方安全计算协议，不仅填补了异步与同步设置之间在通信效率上的差距，这对于构建可信赖的分布式系统和多方安全计算具有深远影响。相关2项研究成果均发表在CRYPTO 2024上。
1.Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience, Xiaoyu Ji, Junru Li, Yifan Song, https://eprint.iacr.org/2024/243, CRYPTO 2024.
2. Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience, Vipul Goyal, Chen-Da Liu-Zhang, and Yifan Song, https://eprint.iacr.org/2024/245, CRYPTO 2024.
02 课题组简介
宋一凡博士现任清华大学助理教授，上海期智研究院PI。2017年于清华大学姚班获得学士学位。2022年在卡内基梅隆大学获得博士学位，师从Vipul Goyal教授。研究兴趣为研究兴趣是理论密码学及其在现实世界中的应用，尤其是高效的多方计算。在密码学领域国际顶级会议CRYPTO、EUROCRYPT、USENIX Security等发表学术成果二十余篇。
03 会议简介
CRYPTO会议，全称国际密码学会议（International Cryptology Conference），是密码学领域最负盛名的会议之一。该会议每年举办一次，旨在汇集全球密码学领域的专家学者，共同探讨密码学的最新研究成果和发展趋势。CRYPTO会议涵盖了密码学的各个方面，包括对称密码学、公钥密码学、数字签名、哈希函数、安全协议等，是密码学领域最重要的交流平台之一。
编辑 | 姜月亮
审核 | 吕厦敏
