Delegable zk-SNARKs with proxies

doi:10.1007/s11704-023-2782-9

Front. Comput. Sci.

2024, Vol. 18

Issue (5) : 185812 https://doi.org/10.1007/s11704-023-2782-9

RESEARCH ARTICLE

Delegable zk-SNARKs with proxies

Jinrui SHA^1,², Shengli LIU^2,³(

)

¹. School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
². State Key Laboratory of Cryptology, Beijing 100878, China
³. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Download: PDF(8703 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 $(μ, k, k ′, k ″)$ . The delegable property of zk-SNARKs allows the prover to delegate its proving ability to $μ$ 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 ′$ -soundness and $k ″$ -zero knowledge by taking into consider of multi-proxies.

We propose a construction of $(μ, 2 t + 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.

Keywords zk-SNARKs secret sharing delegation bilinear groups

Corresponding Author(s): Shengli LIU

Just Accepted Date: 30 May 2023 Issue Date: 14 September 2023

Cite this article:

Jinrui SHA,Shengli LIU. Delegable zk-SNARKs with proxies[J]. Front. Comput. Sci., 2024, 18(5): 185812.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-2782-9
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I5/185812

Fig.1 The

(t + 1, μ)

-secret sharing scheme

SS μ t

by lagrange interpolation

Fig.2 Algorithms

CRSGen

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

Fig.3 Algorithms

DelegableGen

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

Fig.4 Protocol

interact

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

Fig.5 Algorithms

delegableProve

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

Fig.6 Algorithms

delegableVerify

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

Fig.7 Algorithm

Sim

in the

(μ, 2 t + 1, t, t)

-delegable zk-SNARK scheme

1	J, Groth R, Ostrovsky A Sahai . New techniques for noninteractive zero-knowledge. Journal of the ACM, 2012, 59( 3): 1–35
2	J, Groth R, Ostrovsky A Sahai . Non-interactive zaps and new techniques for NIZK. In: Proceedings of the 26th Annual International Cryptology Conference. 2006, 97−111
3	J Groth . 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	J, Groth A Sahai . Efficient noninteractive proof systems for bilinear groups. SIAM Journal on Computing, 2012, 41( 5): 1193–1232
5	J Groth . 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	S, Goldwasser S, Micali C Rackoff . The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 1989, 18( 1): 186–208
7	M, Blum P, Feldman S Micali . Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 103−112
8	J Kilian . 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	S, Arora S Safra . Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 1998, 45( 1): 70–122
10	S Micali . Computationally sound proofs. SIAM Journal on Computing, 2000, 30( 4): 1253–1298
11	A, Fiat A Shamir . 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	N, Bitansky R, Canetti A, Chiesa E Tromer . 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	I, Damgård S, Faust C Hazay . Secure two-party computation with low communication. In: Proceedings of the 9th Theory of Cryptography Conference. 2012, 54−74
15	J Groth . 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	H Lipmaa . 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	R, Gennaro C, Gentry B, Parno M Raykova . 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	N, Bitansky A, Chiesa Y, Ishai O, Paneth R Ostrovsky . Succinct non-interactive arguments via linear interactive proofs. In: Proceedings of the 10th Theory of Cryptography Conference. 2013, 315−333
19	S, Setty B, Braun V, Vu A J, Blumberg B, Parno M Walfish . 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	E, Ben-Sasson A, Chiesa D, Genkin E, Tromer M Virza . SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 90−108
21	G, Danezis C, Fournet J, Groth M Kohlweiss . 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	E, Ben-Sasson A, Chiesa E, Tromer M Virza . Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Conference on Security Symposium. 2014, 781−796
23	M, Backes M, Barbosa D, Fiore R M Reischuk . ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In: Proceedings of 2015 IEEE Symposium on Security and Privacy. 2015, 271−286
24	C, Costello C, Fournet J, Howell M, Kohlweiss B, Kreuter M, Naehrig B, Parno S Zahur . Geppetto: versatile verifiable computation. In: Proceedings of 2015 IEEE Symposium on Security and Privacy. 2015, 253−270
25	A, Chiesa E, Tromer M Virza . 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	J, Groth M, Kohlweiss M, Maller S, Meiklejohn I Miers . Updatable and universal common reference strings with applications to zk-SNARKs. In: Proceedings of the 38th Annual International Cryptology Conference. 2018, 698−728
27	M, Maller S, Bowe M, Kohlweiss S Meiklejohn . 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	A, Chiesa Y, Hu M, Maller P, Mishra N, Vesely N Ward . 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	M, Bellare G, Fuchsbauer A Scafuro . 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	B, Abdolmaleki K, Baghery H, Lipmaa M Zając . 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	G Fuchsbauer . Subversion-zero-knowledge SNARKs. In: Proceedings of the 21st IACR International Workshop on Public Key Cryptography. 2018, 315−347
33	M, Abe S Fehr . Perfect NIZK with adaptive soundness. In: Proceedings of the 4th Theory of Cryptography Conference. 2007, 118−136
34	V Shoup . 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

[1]

FCS-22782-OF-JS_suppl_1

Download

[1]	Lei WU, Fuyou MIAO, Keju MENG, Xu WANG. A simple construction of CRT-based ideal secret sharing scheme and its security extension based on common factor[J]. Front. Comput. Sci., 2022, 16(1): 161811-.
[2]	Zhusen LIU, Zhenfu CAO, Xiaolei DONG, Xiaopeng ZHAO, Haiyong BAO, Jiachen SHEN. A verifiable privacy-preserving data collection scheme supporting multi-party computation in fog-based smart grid[J]. Front. Comput. Sci., 2022, 16(1): 161810-.
[3]	Bingbing JIANG. Multi-key FHE without ciphertext-expansion in two-server model[J]. Front. Comput. Sci., 2022, 16(1): 161809-.
[4]	Keju MENG, Fuyou MIAO, Yu NING, Wenchao HUANG, Yan XIONG, Chin-Chen CHANG. A proactive secret sharing scheme based on Chinese remainder theorem[J]. Front. Comput. Sci., 2021, 15(2): 152801-.
[5]	Yudi ZHANG, Debiao HE, Mingwu ZHANG, Kim-Kwang Raymond CHOO. A provable-secure and practical two-party distributed signing protocol for SM2 signature algorithm[J]. Front. Comput. Sci., 2020, 14(3): 143803-.
[6]	Changpeng ZHU, Yinliang ZHAO, Bo HAN, Qinghua ZENG, Ying MA. Runtime support for type-safe and context-based behavior adaptation[J]. Front. Comput. Sci., 2014, 8(1): 17-32.

Viewed

Full text

Abstract

Cited

Shared

Discussed