Abstract
Non-interactive zero-knowledge (NIZK) proofs have been investigated in two models: the Public Parameter model and the Secret Parameter model. In the former, a public string is “ideally” chosen according to some efficiently samplable distribution and made available to both the Prover and Verifier. In the latter, the parties instead obtain correlated (possibly different) private strings. To add further choice, the definition of zero-knowledge in these settings can either be non-adaptive or adaptive.
In this paper, we obtain several unconditional characterizations of computational, statistical and perfect NIZK for all combinations of these settings. Specifically, we show:
In the secret parameter model, NIZK = NISZK = NIPZK = AM.
In the public parameter model,
– for the non-adaptive definition, NISZK ⊆ AM ∩ coAM,
– for the adaptive one, it also holds that NISZK ⊂ BPP,
– for computational NIZK for “hard” languages, one-way functions are both necessary and sufficient.
From our last result, we arrive at the following unconditional characterization of computational NIZK in the public parameter model (which complements well-known results for interactive zero-knowledge):
Either NIZK proofs exist only for “easy” languages (i.e., languages that are not hard-on-average), or they exist for all of AM (i.e., all languages which admit non-interactive proofs).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aiello, W., Håstad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42, 327–345 (1991)
Aumann, R.: Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 67–96 (1974)
Babai, L., Moran, S.: Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254–276 (1988)
Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Computing 20(6), 1084–1118 (1991)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC 1988, pp. 103–112 (1988)
Boppana, R., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC 2002, pp. 494–503 (2002)
Cramer, R., Damgård, I.: Secret-key zero-knowledge and non-interactive verifiable exponentiation. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 223–237. Springer, Heidelberg (2004)
Damgård, I.: Non-interactive circuit based proofs and non-interactive perfect zero knowledge with preprocessing. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 341–355. Springer, Heidelberg (1993)
Damgård, I.: Efficient concurrent zero-knowledge in the auxiliary string model. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer, Heidelberg (2000)
Damgård, I., Fazio, N., Nicolosi, A.: Secret-key zero-knowledge protocols for NP and applications to threshold cryptography. Manuscript (2005)
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)
De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: Image density is complete for non-interactive-SZK. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 784–795. Springer, Heidelberg (1998)
De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge with preprocessing. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 269–282. Springer, Heidelberg (1988)
Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string. In: FOCS 1990, pp. 308–317 (1990)
Gennaro, R., Micciancio, D., Rabin, T.: An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products. In: CCS 1998, pp. 67–72 (1998)
Goldreich, O.: A note on computational indistinguishability. Inf. Process. Lett. 34(6), 277–281 (1990)
Goldreich, O.: Foundations of Cryptography, vol. I (2001)
Goldreich, O.: Foundations of Cryptography, vol. II (2004)
Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Crypt. 7(1), 1–32 (1994)
Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467–484. Springer, Heidelberg (1999)
Goldreich, O., Vadhan, S.: Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In: Computational Complexity (1998)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985, pp. 291–304 (1985)
Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: STOC 1986, pp. 59–68 (1986)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
Kilian, J.: Founding cryptography on oblivious transfer. In: STOC 1988, pp. 20–31 (1988)
Kilian, J., Micali, S., Ostrovsky, R.: Minimum resource zero-knowledge proofs. In: FOCS 1989, pp. 474–479 (1989)
Kilian, J., Petrank, E.: An efficient non-interactive zero-knowledge proof system for NP with general assumptions. J. Crypt. 11(1), 1–27 (1998)
Naor, M.: Bit commitment using pseudorandomness. J. Crypt. 4(2), 151–158 (1991)
Okamoto, T.: On relationships between statistical zero-knowledge proofs. In: STOC 1996, pp. 649–658 (1996)
Ostrovsky, R., Wigderson, A.: One-way fuctions are essential for non-trivial zero-knowledge. In: ISTCS, pp. 3–17 (1993)
Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196–249 (2003)
De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge proof systems. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 52–72. Springer, Heidelberg (1988)
Vadhan, S.: A Study of Statistical Zero-Knowledge Proofs. PhD thesis, MIT (1999)
Vadhan, S.: An unconditional study of computational zero knowledge. In: FOCS 2004, pp. 176–185 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pass, R., shelat, a. (2005). Unconditional Characterizations of Non-interactive Zero-Knowledge. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_8
Download citation
DOI: https://doi.org/10.1007/11535218_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)