Shorter ZK-SNARKs from square span programs over ideal lattices  

作　　者：Xi Lin Heyang Cao Feng‑Hao Liu Zhedong Wang Mingsheng Wang 

机构地区：[1]Key Laboratory of Cyberspace Security Defense,Institute of Information Engineering,Chinese Academy of Sciences,Beijing,China [2]School of Cyber Security,University of Chinese Academy of Sciences,Beijing,China [3]School of Electrical Engineering&Computer Science,Washington State University,Pullman,WA,USA [4]School of Cyber Science and Engineering,Shanghai Jiaotong University,Shanghai,China

出　　处：《Cybersecurity》2025年第1期208-226,共19页网络空间安全科学与技术(英文)

基　　金：supported by the National Key R&D Program of China under Grant 2020YFA0712303;Zhedong Wang is supported by National Natural Science Foundation of China(Grant No.62202305);Shanghai Pujiang Program under Grant 22PJ1407700.

摘　　要：Zero-knowledge succinct non-interactive arguments of knowledge(zk-SNARKs)are cryptographic protocols that ofer efcient and privacy-preserving means of verifying NP language relations and have drawn considerable atten‑tion for their appealing applications,e.g.,verifable computation and anonymous payment protocol.Compared with the pre-quantum case,the practicability of this primitive in the post-quantum setting is still unsatisfactory,espe‑cially for the space complexity.To tackle this issue,this work seeks to enhance the efciency and compactness of lat‑tice-based zk-SNARKs,including proof length and common reference string(CRS)length.In this paper,we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings.Compared with previous works,our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes.Particularly,the proof length of our scheme is around 23.3%smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al.(in:Proceedings of the 2021 ACM SIGSAC conference on computer and communications security,pp 212-234,2021),and the CRS length is 3.6×smaller.Our constructions follow the framework of Gennaro et al.(in:Proceedings of the 2018 ACM SIGSAC conference on computer and com‑munications security,pp 556-573,2018),and adapt it to the ring setting by slightly modifying the knowledge assumptions.We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.

关 键 词：Zk-SNARKs Post-quantum Succinct argument 

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