Delegable zk-SNARKs with proxies

Abstract

In this paper, we propose the concept of delegable zero knowledge succinct non-interactive arguments of knowledge (zk-SNARKs). The delegable zk-SNARK is parameterized by (\mu ,k,k^{\prime },k^{″}). The delegable property of zk-SNARKs allows the prover to delegate its proving ability to \mu proxies. Any k honest proxies are able to generate the correct proof for a statement, but the collusion of less than k proxies does not obtain information about the witness of the statement. We also define k^{\prime }-soundness and k^{″}-zero knowledge by taking into consider of multi-proxies.

We propose a construction of (\mu ,2t+1,t,t)- delegable zk-SNARK for the NPC language of arithmetic circuit satisfiability. Our delegable zk-SNARK stems from Groth’s zk-SNARK scheme (Groth16). We take advantage of the additive and multiplicative properties of polynomial-based secret sharing schemes to achieve delegation for zk-SNARK. Our secret sharing scheme works well with the pairing groups so that the nice succinct properties of Groth’s zk-SNARK scheme are preserved, while augmenting the delegable property and keeping soundness and zero-knowledge in the scenario of multi-proxies.

Graphical abstract

Keywords

zk-SNARKs / secret sharing / delegation / bilinear groups

JinRui Sha received the BS degree from School of Cyber Science and Engineering in Shanghai Jiao Tong University, China in 2019. He is working toward the PhD degree in Shanghai Jiao Tong University, China. His research interests include zero knowledge proof

Shengli Liu received the PhD degree in cryptography from Xidian University, China in 2000 and another PhD degree from Eindhoven University of Technology, Netherlands in 2002. She is a professor in Shanghai Jiao Tong University, China. Her research interests include cryptography and information security

References

[1] Groth J, Ostrovsky R, Sahai A . New techniques for noninteractive zero-knowledge. Journal of the ACM, 2012, 59( 3): 1–35

[2] Groth J, Ostrovsky R, Sahai A. Non-interactive zaps and new techniques for NIZK. In: Proceedings of the 26th Annual International Cryptology Conference. 2006, 97−111

[3] Groth J. Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Proceedings of the 12th International Conference on the Theory and Application of Cryptology and Information Security. 2006, 444−459

[4] Groth J, Sahai A . Efficient noninteractive proof systems for bilinear groups. SIAM Journal on Computing, 2012, 41( 5): 1193–1232

[5] Groth J. On the size of pairing-based non-interactive arguments. In: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2016, 305−326

[6] Goldwasser S, Micali S, Rackoff C . The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 1989, 18( 1): 186–208

[7] Blum M, Feldman P, Micali S. Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 103−112

[8] Kilian J. A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. 1992, 723−732

[9] Arora S, Safra S . Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 1998, 45( 1): 70–122

[10] Micali S . Computationally sound proofs. SIAM Journal on Computing, 2000, 30( 4): 1253–1298

[11] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems. In: Proceedings of Conference on the Theory and Application of Cryptographic Techniques. 1986, 186−194

[12] Bitansky N, Canetti R, Chiesa A, Tromer E. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, 326−349

[13] Goldwasser S, Lin H, Rubinstein A. Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, 2011

[14] Damgård I, Faust S, Hazay C. Secure two-party computation with low communication. In: Proceedings of the 9th Theory of Cryptography Conference. 2012, 54−74

[15] Groth J. Short pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. 2010, 321−340

[16] Lipmaa H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security. 2013, 41−60

[17] Gennaro R, Gentry C, Parno B, Raykova M. Quadratic span programs and succinct NIZKs without PCPs. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 626−645

[18] Bitansky N, Chiesa A, Ishai Y, Paneth O, Ostrovsky R. Succinct non-interactive arguments via linear interactive proofs. In: Proceedings of the 10th Theory of Cryptography Conference. 2013, 315−333

[19] Setty S, Braun B, Vu V, Blumberg A J, Parno B, Walfish M. Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th ACM European Conference on Computer Systems. 2013, 71−84

[20] Ben-Sasson E, Chiesa A, Genkin D, Tromer E, Virza M. SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 90−108

[21] Danezis G, Fournet C, Groth J, Kohlweiss M. Square span programs with applications to succinct NIZK arguments. In: Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security. 2014, 532−550

[22] Ben-Sasson E, Chiesa A, Tromer E, Virza M. Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Conference on Security Symposium. 2014, 781−796

[23] Backes M, Barbosa M, Fiore D, Reischuk R M. ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In: Proceedings of 2015 IEEE Symposium on Security and Privacy. 2015, 271−286

[24] Costello C, Fournet C, Howell J, Kohlweiss M, Kreuter B, Naehrig M, Parno B, Zahur S. Geppetto: versatile verifiable computation. In: Proceedings of 2015 IEEE Symposium on Security and Privacy. 2015, 253−270

[25] Chiesa A, Tromer E, Virza M. Cluster computing in zero knowledge. In: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2015, 371−403

[26] Groth J, Kohlweiss M, Maller M, Meiklejohn S, Miers I. Updatable and universal common reference strings with applications to zk-SNARKs. In: Proceedings of the 38th Annual International Cryptology Conference. 2018, 698−728

[27] Maller M, Bowe S, Kohlweiss M, Meiklejohn S. Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In: Proceedings of 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019, 2111−2128

[28] Chiesa A, Hu Y, Maller M, Mishra P, Vesely N, Ward N. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 738−768

[29] Gabizon A, Williamson Z J, Ciobotaru O. PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, 2019

[30] Bellare M, Fuchsbauer G, Scafuro A. NIZKs with an untrusted CRS: security in the face of parameter subversion. In: Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security. 2016, 777−804

[31] Abdolmaleki B, Baghery K, Lipmaa H, Zając M. A subversion-resistant SNARK. In: Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security. 2017, 3−33

[32] Fuchsbauer G. Subversion-zero-knowledge SNARKs. In: Proceedings of the 21st IACR International Workshop on Public Key Cryptography. 2018, 315−347

[33] Abe M, Fehr S. Perfect NIZK with adaptive soundness. In: Proceedings of the 4th Theory of Cryptography Conference. 2007, 118−136

[34] Shoup V. Lower bounds for discrete logarithms and related problems. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 1997, 256−266

[35] Dent A W. The hardness of the DHK problem in the generic group model. Cryptology ePrint Archive, 2006

Acknowledgements

Shengli Liu and Jinrui Sha were partially sponsored by the National Key R&D Program of China (No. 2022YFB2701503), the National Natural Science Foundation of China (Grant No. 61925207) and Guangdong Major Project of Basic and Applied Basic Research (No. 2019B030302008).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2024 Higher Education Press