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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
We stress that this extractor interacts with the malicious authority online without being able to rewind it. This is because, in the real world, we cannot rewind such an authority.
- 2.
By “sparse” we mean that \(L \subseteq \varSigma \) of some domain \(\varSigma \), and \(|L| / |\varSigma |\) is exponentially small in the security parameter.
- 3.
In our construction, S can be set to be \(2^{\omega (\log \lambda )}\) assuming \(2^{\lambda ^{\epsilon }}\)-hardness of either a one-way permutation or a collision-resistant hash function.
References
Zero-knowledge contingency payment. https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment. Accessed Feb 2023
Ananth, P., Asharov, G., Dahari, H., Goyal, V.: Towards accountability in CRS generation. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 278–308. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_10
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
Barak, B., Pass, R.: On the possibility of one-message weak zero-knowledge. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 121–132. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_7
Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 777–804. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_26
Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. Cryptology ePrint Archive, Paper 2014/349 (2014)
Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: On the existence of extractable one-way functions. Cryptology ePrint Archive, Paper 2014/402 (2014). https://doi.org/10.1145/2591796.2591859, https://eprint.iacr.org/2014/402, https://eprint.iacr.org/2014/402
Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123–152. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_5
Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991). https://doi.org/10.1137/0220068
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)
Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 573–592. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_34
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)
Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_16
Chor, B., Fiat, A., Naor, M.: Tracing traitors. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 257–270. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_25
Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513–1543 (2007)
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)
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)
Garg, S., Goyal, V., Jain, A., Sahai, A.: Bringing people of different beliefs together to do UC. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 311–328. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_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)
Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1–32 (1994)
Goyal, R., Kim, S., Manohar, N., Waters, B., Wu, D.J.: Watermarking public-key cryptographic primitives. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 367–398. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_12
Goyal, R., Kim, S., Waters, B., Wu, D.J.: Beyond software watermarking: traitor-tracing for pseudorandom functions. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 250–280. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_9
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)
Goyal, V.: Reducing trust in the PKG in identity based cryptosystems. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 430–447. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_24
Groth, J., Ostrovsky, R.: Cryptography in the multi-string model. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 323–341. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_18
Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_6
Kuykendall, B., Zhandry, M.: Towards non-interactive witness hiding. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 627–656. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_22
Nishimaki, R., Wichs, D., Zhandry, M.: Anonymous traitor tracing: How to embed arbitrary information in a key. Cryptology ePrint Archive, Paper 2015/750 (2015)
Pass, R.: Simulation in quasi-polynomial time, and its application to protocol composition. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 160–176. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_10
Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4
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)
Acknowledgements
This work was done partially when Pratik Soni was visiting Carnegie Mellon University, where he was supported by a DARPA SIEVE grant, and an ACE center award from the Algorand Foundation. Gilad Asharov and Hadar Kaner were supported by Israel Science Foundation (grant No. 2439/20), JP Morgan Faculty Research Award, and European Union’s Horizon 2020 research and innovation programme under the Marie SklodowskaCurie grant agreement No. 891234. Prabhanjan Ananth is supported by the National Science Foundation under Grant No. 2329938 and Grant No. 2341004.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ananth, P., Asharov, G., Goyal, V., Kaner, H., Soni, P., Waters, B. (2024). NIZKs with Maliciously Chosen CRS: Subversion Advice-ZK and Accountable Soundness. In: Galdi, C., Phan, D.H. (eds) Security and Cryptography for Networks. SCN 2024. Lecture Notes in Computer Science, vol 14973. Springer, Cham. https://doi.org/10.1007/978-3-031-71070-4_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-71070-4_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-71069-8
Online ISBN: 978-3-031-71070-4
eBook Packages: Computer ScienceComputer Science (R0)