零知识证明递归与复合技术研究综述  

A Survey on Recursive and Composite Techniques of Zero-Knowledge Proofs

作　　者：张宗洋 周子博 邓燚[2,3] ZHANG Zong-Yang;ZHOU Zi-Bo;DENG Yi(School of Cyber Science and Technology,Beihang University,Beijing 100191;Key Laboratory of Cyberspace Security Defense,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093;School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049)

机构地区：[1]北京航空航天大学网络空间安全学院,北京100191 [2]中国科学院信息工程研究所网络空间安全防御重点实验室,北京100093 [3]中国科学院大学网络空间安全学院,北京100049

出　　处：《计算机学报》2024年第10期2466-2490,共25页Chinese Journal of Computers

基　　金：国家重点研发计划(2022YFB2702702);国家自然科学基金项目(62372020,61972017,72031001,61932019,62372447);北京市自然科学基金(M22038,L222050,M21033);中央高校基本科研业务费(YWF-23-L-1032);北航博士研究生国际联合培养基金资助。

摘　　要：零知识证明作为一种重要的密码学协议,是实现数据安全流通的关键技术之一.其允许证明者向验证者证明某个断言的正确性,而又不泄露任何额外信息.零知识证明所描述的断言可划分成代数断言、非代数断言和复合断言,而递归与复合技术可以极大地提高零知识证明协议的性能并深入拓展其功能,是当前的研究热点.本文系统且全面地研究了零知识证明的递归与复合技术.首先,在针对代数断言的递归零知识证明方面,全面研究了关于内积关系的递归零知识证明协议,并从证明复杂度、通信复杂度、验证复杂度等角度对比分析了基于Pedersen承诺方案的内积论证协议.其次,在针对非代数断言的递归零知识证明方面,全面梳理了增量可验证计算方案与基于电路的证明系统组合这两种主流应用的研究现状,并对比分析了增量可验证计算方案的复杂度、关键技术及实现方案等.然后,在针对复合断言的复合零知识证明方面,从复杂度、启动阶段、关键模块等角度对比分析了承诺并证明的零知识证明协议.最后,给出了零知识证明递归与复合技术的未来研究方向.Zero-knowledge proofs,as a fundamental cryptographic primitive,allow one party in a communication to prove the validity of a certain statement to another party without revealing any additional information.They are pivotal technologies for the secure circulation of data and play an extremely important role in cryptography and security.They are not only critical components of many cryptographic protocols,such as authentication,digital signature,and public-key encryption,but also provide significant privacy protection and performance enhancement for various practical applications,including anonymous transactions,smart contracts,machine learning,and more.In general,the statements to be proven by zero-knowledge proofs are categorized into three types:algebraic statements,non-algebraic statements,and composite statements involving both algebraic and non-algebraic statements.Although zero-knowledge proof protocols for these statements have made significant progress in terms of performance,functionality,etc.,there remain challenges in practical applications,such as insufficient efficiency,poor scalability,and specialized functionality.To effectively address these bottleneck issues,the techniques of recursion and composition in zero-knowledge proofs have received extensive attention in recent years.In this paper,we conduct a systematic and comprehensive survey on the recursive and composite techniques of zero-knowledge proofs.Firstly,regarding recursive zero-knowledge proofs for algebraic statements,inner product arguments,a kind of ∑-protocols proving that the inner product of two committed vectors equals a public scalar,firstly rely on recursive techniques to achieve a breakthrough in communication complexity,reducing it from linear to logarithmic.We extensively survey inner product arguments,comparing and analyzing them in detail,particularly those based on the Pedersen commitment scheme.This analysis is conducted from the perspectives of prover complexity,communication complexity,verifier complexity,and more.Secondl

关 键 词：零知识证明 递归零知识证明 内积论证 增量可验证计算方案 复合零知识证明 承诺并证明的零知识证明 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]