宋一凡

上海期智研究院PI，清华大学交叉信息研究院助理教授。

2017年于清华大学姚班获得学士学位。2022年在卡内基梅隆大学获得博士学位，师从Vipul Goyal教授。研究兴趣为研究兴趣是理论密码学及其在现实世界中的应用，尤其是高效的多方计算。在密码学领域国际顶级会议CRYPTO、EUROCRYPT、USENIX Security等发表学术成果二十余篇。

多方安全计算：研究理论多方安全计算协议在各种模型下的复杂度

隐私电路：构建可以防范各类信息泄漏的隐私电路。

成果2：在异步网络下构建具有线性复杂度的多方安全计算协议（2024年度）

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

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

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

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

------------------------------------------------------------------------------------------------------------------------------

成果1：可容忍泄露的隐私电路（2024年度）

       对于一类泄露函数L，可容忍泄露的隐私电路要求对于电路内部的任意L范围内的信息泄露可以规约到对于输入和输出的L范围内的信息泄露。可容忍泄露的隐私数据可以被用来设计安全硬件以防范侧信道攻击并提供理论基础。宋一凡团队给出了首个针对计算深度1的全局泄露函数类的可容忍泄露隐私电路的构造，同时团队给出了从无状态隐私电路到有状态隐私电路的一般性构造。

       密码学中的一个理想目标是设计一个可以对隐私数据做一般计算任务的电路/硬件使得它可以天然的防范任意的侧信道攻击，这一目标被抽象为隐私电路。隐私电路一般可分为两类，第一类是可抵御泄露的隐私电路，对于某一类泄露函数L，它要求任意关于电路内部的L范围内的信息泄露与隐私数据无关，这类隐私电路天然的需要对隐私数据进行初始的加工；第二类是可容忍泄露的隐私电路，对于某一类泄露函数L，它要求任意关于电路内部的L范围内的信息泄露可以规约到对于输入和输出的L范围内的信息泄露。在这项工作中，团队主要关注后者。注意到后者不需要对输入输出进行任何加工，这意味着当侧信道攻击局限于L中的泄露函数时，可容忍泄露的隐私电路可以被视为一个理想的安全硬件（即其内部对外不可见）。

       宋一凡团队给出了首个针对全局泄露函数类的可容忍泄露隐私电路的构造，具体而言，该构造可以防范深度1的泄露函数类（逻辑与、或、异或）。同时团队给出了从无状态可容忍泄露的隐私电路到有状态可抵御泄露的隐私电路的一般构造，对于深度1的泄露函数类，首次实现有状态可抵御泄露的隐私电路大小与泄露数据量成次平方关系。

论文信息：Leakage-Tolerant Circuits，Yuval Ishai, and Yifan Song

项目链接：https://eprint.iacr.org/2024/332