信息学院张良峰课题组在多服务器非交互式可验证计算研究方面取得重要进展

第43届IEEE安全与隐私研讨会（Symposium on Security and Privacy，IEEE S&P 2022）将于2022年5月在美国奥克兰举行，以信息学院张良峰教授作为第一作者兼通讯作者的两人研究团队提交的题为“Multi-Server Verifiable Computation of Low-Degree Polynomials”的论文被该会议全文录用。

可验证计算允许计算能力较弱的用户将复杂计算任务委托（外包）给计算资源密集的云服务器并对云服务器计算过程的正确性进行验证。自从图灵奖获得者Shafi Goldwasser等人在2008年针对特殊函数构造多项式时间可证明、准线性时间可验证的非交互式证明系统以来，非交互式可验证计算技术已成为信息安全研究的热点。此类技术的核心要求是服务器必须向用户证明其计算过程的正确性，并且用户验证时间必须严格小于其自行执行计算任务所消耗的时间。同时确保计算结果的完整性和用户数据的隐私性是极具挑战性的难题。IACR Fellow、著名密码学家Rafail Ostrovsky等人曾经指出，非交互式单服务器可验证计算在实现数据隐私性时须借助于同态加密等低效密码学原语，从而受制于现有技术的局限，无法达到应用级效率。现有工作在多服务器可验证计算模型下寻求突破时需要服务器之间进行极为复杂的交互过程。Rafail Ostrovsky等人将构造服务器之间非交互的多服务器可验证计算方案确定为公开问题。

研究团队针对多元低次多项式函数解决了这一公开问题。基于不同思路，他们设计了五个公开可委托的解决方案，其中三个为私有可验证，两个为公开可验证。私有可验证方案实现了信息论意义下的数据隐私性与计算完整性，公开可验证方案实现了信息论意义下的数据隐私性、基于标准数论假设的计算完整性。解决方案抵近应用级效率，在实现百万项多项式计算时，所设计的方案中用户验证时间开销不超过2ms，单服务器最大开销不超过1s, 多服务器总开销不超过5s，比现有最好水平加速300倍以上，在可验证私有信息检索、可验证隐私函数/数据计算等应用中具有直接应用价值。

该论文是张良峰课题组针对上述公开问题进行研究所得到的第二项重要研究成果。此前张良峰教授曾作为唯一作者在CCF A类、计算机科学理论顶级期刊Information and Computation（IANDC）上发表题为“Multi-Server Verifiable Delegation of Computations: Unconditional Security and Practical Efficiency” 的论文，解决了同一模型下线性函数的计算问题。论文的第一完成单位为上海科技大学，得到了上海科技大学科研启动基金、上海市自然科学基金、国家自然科学基金的资助。  

IEEE S&P是计算机安全领域四大顶级会议之一，收录研究机构以及科技企业在计算机安全和隐私研究领域最前沿、最顶级的研究成果，每年在美国奥克兰召开，又称奥克兰会议。IEEE S&P始于1980年，历史悠久，录用率长期保持在12%左右，发表难度极高。据统计，在过去42年的会议中，中国大陆研究机构和科技企业作为第一完成单位发表的论文不超过30篇。