NIZKs with Maliciously Chosen CRS: Subversion Advice-ZK and Accountable Soundness
Authors: 
Prabhanjan Ananth, 
Gilad Asharov, Vipul Goyal, Hadar Kaner, Pratik Soni, 
Brent WatersAuthors Info & Claims
Pages 3 - 23
Abstract
Trusted setup is commonly used for non-interactive proof and argument systems. However, there is no guarantee that the setup parameters in these systems are generated in a trustworthy manner. Building upon previous works, we conduct a systematic study of non-interactive zero-knowledge arguments in the common reference string model where the authority running the trusted setup might be corrupted. We explore both zero-knowledge and soundness properties in this setting.
•
We consider a new notion of NIZK called subversion advice-ZK NIZK that strengthens the notion of zero-knowledge with malicious authority security considered by Ananth, Asharov, Dahari and Goyal (EUROCRYPT’21), and present a construction of a subversion advice-ZK NIZK from the sub-exponential hardness of learning with errors.
•
We introduce a new notion that strengthens the traditional definition of soundness, called accountable soundness, and present generic compilers that lift any NIZK for interesting languages in NP to additionally achieve accountable soundness.
•
Finally, we combine our results for both subversion advice-ZK and accountable soundness to achieve a subversion advice-ZK NIZK that also satisfies accountable soundness. This results in the first NIZK construction that satisfies meaningful notions of both soundness and zero-knowledge even for maliciously chosen CRS.
References
[1]
Zero-knowledge contingency payment. https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment. Accessed Feb 2023
[2]
Ananth P, Asharov G, Dahari H, and Goyal V Canteaut A and Standaert F-X Towards accountability in CRS generation Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 278-308
[3]
Ananth, P., Asharov, G., Goyal, V., Kaner, H., Soni, P., Waters, B.: NIZKs with maliciously chosen CRS: subversion advice-ZK and accountable soundness. Cryptology ePrint Archive, Paper 2024/207 (2024). https://eprint.iacr.org/2024/207, https://eprint.iacr.org/2024/207
[4]
Barak B and Pass R Naor M On the possibility of one-message weak zero-knowledge Theory of Cryptography 2004 Heidelberg Springer 121-132
[5]
Bellare M, Fuchsbauer G, and Scafuro A Cheon JH and Takagi T NIZKs with an untrusted CRS: security in the face of parameter subversion Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 777-804
[6]
Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. Cryptology ePrint Archive, Paper 2014/349 (2014)
[7]
Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: On the existence of extractable one-way functions. Cryptology ePrint Archive, Paper 2014/402 (2014)., https://eprint.iacr.org/2014/402, https://eprint.iacr.org/2014/402
[8]
Block AR, Holmgren J, Rosen A, Rothblum RD, and Soni P Malkin T and Peikert C Time- and space-efficient arguments from groups of unknown order Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 123-152
[9]
Blum M, De Santis A, Micali S, and Persiano G Noninteractive zero-knowledge SIAM J. Comput. 1991 20 6 1084-1118
[10]
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Simon, J. (ed.) STOC - Symposium on Theory of Computation, pp. 103–112. ACM (1988)
[11]
Boneh D, Sahai A, and Waters B Vaudenay S Fully collusion resistant traitor tracing with short ciphertexts and private keys Advances in Cryptology - EUROCRYPT 2006 2006 Heidelberg Springer 573-592
[12]
Canetti, R., et al.: Fiat-shamir: from practice to theory. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1082–1090. STOC 2019, Association for Computing Machinery, New York, NY, USA (2019)
[13]
Canetti R, Halevi S, and Katz J Biham E A forward-secure public-key encryption scheme Advances in Cryptology — EUROCRYPT 2003 2003 Heidelberg Springer 255-271
[14]
Chor B, Fiat A, and Naor M Desmedt YG Tracing traitors Advances in Cryptology — CRYPTO ’94 1994 Heidelberg Springer 257-270
[15]
Dwork C and Naor M Zaps and their applications SIAM J. Comput. 2007 36 6 1513-1543
[16]
Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string. In: Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, vol. 1, pp. 308–317 (1990)
[17]
Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 416–426 (1990)
[18]
Garg S, Goyal V, Jain A, and Sahai A Ishai Y Bringing people of different beliefs together to do UC Theory of Cryptography 2011 Heidelberg Springer 311-328
[19]
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 218–229. STOC 1987, Association for Computing Machinery, New York, NY, USA (1987)
[20]
Goldreich O and Oren Y Definitions and properties of zero-knowledge proof systems J. Cryptol. 1994 7 1 1-32
[21]
Goyal R, Kim S, Manohar N, Waters B, and Wu DJ Boldyreva A and Micciancio D Watermarking public-key cryptographic primitives Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 367-398
[22]
Goyal R, Kim S, Waters B, and Wu DJ Tibouchi M and Wang H Beyond software watermarking: traitor-tracing for pseudorandom functions Advances in Cryptology – ASIACRYPT 2021 2021 Cham Springer 250-280
[23]
Goyal, R., Koppula, V., Waters, B.: Collusion resistant traitor tracing from learning with errors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 660-670. STOC 2018, Association for Computing Machinery, New York, NY, USA (2018)
[24]
Goyal V Menezes A Reducing trust in the PKG in identity based cryptosystems Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 430-447
[25]
Groth J and Ostrovsky R Menezes A Cryptography in the multi-string model Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 323-341
[26]
Groth J, Ostrovsky R, and Sahai A Dwork C Non-interactive zaps and new techniques for NIZK Advances in Cryptology - CRYPTO 2006 2006 Heidelberg Springer 97-111
[27]
Kuykendall B and Zhandry M Pass R and Pietrzak K Towards non-interactive witness hiding Theory of Cryptography 2020 Cham Springer 627-656
[28]
Nishimaki, R., Wichs, D., Zhandry, M.: Anonymous traitor tracing: How to embed arbitrary information in a key. Cryptology ePrint Archive, Paper 2015/750 (2015)
[29]
Pass R Biham E Simulation in quasi-polynomial time, and its application to protocol composition Advances in Cryptology — EUROCRYPT 2003 2003 Heidelberg Springer 160-176
[30]
Peikert C and Shiehian S Boldyreva A and Micciancio D Noninteractive zero knowledge for NP from (plain) learning with errors Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 89-114
[31]
Yao, A.C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, pp. 162–167. IEEE Computer Society (1986)
Index Terms
- NIZKs with Maliciously Chosen CRS: Subversion Advice-ZK and Accountable Soundness
Index terms have been assigned to the content through auto-classification.
Recommendations
Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings
AbstractIn a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. A useful relaxation of NIZK is a designated verifier NIZK (DV-NIZK) proof, where ...
Compact NIZKs from Standard Assumptions on Bilinear Maps
AbstractA non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based ...
Dual-Mode NIZKs from Obfuscation
Advances in Cryptology – ASIACRYPT 2019AbstractTwo standard security properties of a non-interactive zero-knowledge (NIZK) scheme are soundness and zero-knowledge. But while standard NIZK systems can only provide one of those properties against unbounded adversaries, dual-mode NIZK systems ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
400 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 11 September 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in