Simulation extractable SNARKs based on target linearly collision-resistant oracle  

作　　者：WANG LiGuan LI Yuan ZHANG ShuangJun CAI DongLiang KAN HaiBin 

机构地区：[1]Shanghai Key Laboratory of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 200433,China [2]Shanghai Engineering Research Center of Blockchain,Shanghai 200433,China [3]Yiwu Research Institute of Fudan University,Yiwu 322000,China

出　　处：《Science China(Technological Sciences)》2024年第9期2853-2866,共14页中国科学（技术科学英文版）

基　　金：supported by the National Key R&D Program of China(Grant No.2019YFB2101703);the National Natural Science Foundation of China(Grant Nos.62272107 and U19A2066);the Innovation Action Plan of Shanghai Science and Technology(Grant No.21511102200);the Key R&D Program of Guangdong Province(Grant No.2020B0101090001)。

摘　　要：The famous zero-knowledge succinct non-interactive arguments of knowledge(zk-SNARK) was proposed by Groth in 2016.Typically, the construction is based on quadratic arithmetic programs which are highly efficient concerning the proof length and the verification complexity. Since then, there has been much progress in designing zk-SNARKs, achieving stronger security,and simulated extractability, which is analogous to non-malleability and has broad applications. In this study, following Groth's pairing-based zk-SNARK, a simulation extractability zk-SNARK under the random oracle model is constructed. Our construction relies on a newly proposed property named target linearly collision-resistant, which is satisfied by random oracles under discrete logarithm assumptions. Compared to the original Groth16 zk-SNARK, in our construction, both parties are allowed to use such a random oracle, aiming to get the same random number. The resulting proof consists of 3 group elements and only 1 pairing equation needs to be verified. Compared to other related works, our construction is shorter in proof length and simpler in verification while preserving simulation extractability. The results also extend to achieve subversion zero-knowledge SNARKs.

关 键 词：quadratic arithmetic program simulation extractability subversion zero-knowledge succinct non-interactive arguments of knowledge target linearly collision-resistant 

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