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

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

RIGHTS & PERMISSIONS

Higher Education Press