宋一凡团队在异步网络下构建具有线性复杂度的多方安全计算协议

       上海期智研究院PI、清华大学助理教授宋一凡，近期在异步网络模型中提出了一种新的基于秘密分享的无条件多方安全计算协议，首次实现每个电路门的开销为与参与方数量成线性关系的通讯量以及进行常数次秘密分享。同时，团队给出了首个线性复杂度的秘密分享机制。将两者结合，团队首次实现了在异步网络下通讯复杂度与参与方数量成线性关系的多方安全计算协议。对分布式系统和多方安全计算方向具有重要价值。相关2项成果收录在Crypto 2024中。

Achievements Summary

       多方安全计算允许互不信任的若干个参与方利用各自的隐私数据完成一个共同的计算任务，Ben-Or、Canetti、Goldreich [STOC’ 93]和Ben-Or、Kelmer、Rabin [PODC’ 94]最早奠基了多方安全计算协议在异步网络下的可行性。在这之后，尽管有很多工作在提升协议的通讯效率，目前在无条件安全以及最优恶意参与方数量的情况下取得的最好结果对于每个电路门的通讯量仍与参与方数量的四次方成正比，与之相对的，在同步网络模型下，最好结果对于每个电路门的通讯量仅与参与方数量呈线性关系。

       宋一凡团队在异步网络模型下提出了一种新的基于秘密分享的无条件安全的多方安全计算协议，这个协议对于每个电路门的开销为与参与方数量成线性关系的通讯量以及进行常数次秘密分享，在此之前，最好的工作[IEEE Trans. Inf. Theory’ 17]需要参与方数量平方关系的通讯量以及进行参与方数量成线性关系次的秘密分享。在上述成果基础上，团队在异步网络下给出首个线性复杂度的秘密分享机制，在此之前，最好的工作[J.Crypto’ 23]需要参与方数量立方关系的通讯量。将两个成果相结合，团队给出了首个在异步网络下通讯复杂度与参与方数量成线性关系的多方安全计算协议，这与已知的同步网络模型下的多方安全协议的通讯复杂度相当。这项工作为在不依赖同步时钟和网络延迟的环境下实现高效、安全的多方计算提供了可能，在理论上和实践上都具有重要意义。

       技术上讲，异步网络模型的主要困难在于保证协议能够顺利运行并终止（Liveness），造成这个困难的原因是当一个参与方没有接收到另一个参与方的信息时，我们无法判断是由于网络延迟造成信息尚未送达还是恶意参与方拒绝参与协议。为了避免因恶意参与方拒绝参与协议而导致协议无限等待，参与方只能期待接收诚实参与方数量的信息后就继续执行；但另一方面，未接收到的信息可能是因为网络延迟造成，而接收到的一部分信息反而来自恶意参与方，这使得异步网络模型下的协议对于恶意参与方数量的容忍度要低于同步网络下的协议，同时也为协议的构造带来巨大的障碍。为了克服这个困难，宋一凡团队提出两个更加高效但均无法保证终止的协议，其中第一个协议的终止需要有足够多的恶意参与方参与，而第二个协议的终止需要有足够少的恶意参与方参与，通过将两个协议巧妙地联系在一起，每个参与方需要先参加第一个协议才能参加第二个协议，这使得无论攻击者的策略如何，至少有一个协议的终止条件得到满足。

       宋一凡团队提出的异步网络下构建具有线性复杂度的多方安全计算协议，不仅填补了异步与同步设置之间在通信效率上的差距，这对于构建可信赖的分布式系统和多方安全计算具有深远影响。相关2项研究成果均发表在CRYPTO 2024上。