Abstract
We show that the class NISZK of languages that admit non-interactive statistical zero-knowledge proof system has a natural complete promise problem. This characterizes statistical zero-knowledge in the public random string model without reference to the public random string or to zero knowledge.
Building on this result we are able to show structural properties of NISZK such as closure under OR composition and closure under complement.
Preview
Unable to display preview. Download preview PDF.
References
W. Aiello and J. Håstad, Statistical Zero Knowledge Can Be Recognized in Two Rounds, Journal of Computer and System Sciences, 42, 1991, pp. 327–345.
W. Aiello, M. Bellare and R. Venkatesan, Knowledge on the average — Perfect, Statistical and Logarithmic, in Proc. of STOC 95.
L. Babai and S. Moran, Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes, Journal of Computer and System Sciences, vol. 36, 1988, pp. 254–276.
M. Ben-Or, O. Goldreich, S. Goldwasser, J. Håstad, J. Kilian, S. Micali, and P. Rogaway, Everything Provable is Provable in Zero Knowledge, in CRYPTO 88.
M. Blum, A. De Santis, S. Micali, and G. Persiano, Non-Interactive Zero-Knowledge, SIAM Journal of Computing, vol. 20, no. 6, Dec 1991, pp. 1084–1118.
M. Blum, P. Feldman, and S. Micali, Non-Interactive Zero-Knowledge and Applications, in STOC 88.
L. Carter and M. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences, vol. 18, 1979, pp. 143–154.
A. De Santis, G. Di Crescenzo, G. Persiano, The Knowledge Complexity of Quadratic Residuosity Languages, Theoretical Computer Science, vol. 132, (1994), pag. 291–317.
A. De Santis, G. Di Crescenzo, G. Persiano, Randomness-Efficient Non-Interactive Zero-Knowledge, in Proc. of ICALP 97.
A. De Santis, G. Di Crescenzo, P. Persiano, and M. Yung, On Monotone Formula Closure of SZK, in FOCS 94.
L. Fortnow, The Complexity of Perfect Zero Knowledge, in STOC 87.
M. Garey e D. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979.
O. Goldreich, S. Micali, and A. Wigderson, Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems, Journal of the ACM, vol. 38, n. 1, 1991, pp. 691–729.
O. Goldreich and Y. Oren, Definitions and Properties of Zero-Knowledge Proof Systems, Journal of Cryptology, v. 7, n. 1, 1994.
S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof-Systems, SIAM Journal on Computing, vol. 18, n. 1, February 1989.
S. Goldwasser and M. Sipser, Private Coins versus Public Coins in Interactive Proof-Systems, in STOC 1986.
J. Håstad, R. Impagliazzo, L. Levin, and M. Luby, Construction of a Pseudo-Random Generator from One-Way Function, to appear in SIAM J. on Computing.
R. Impagliazzo and M. Yung, Direct Minimum Knowledge Computations, in CRYPTO 87.
R. Impagliazzo and D. Zuckerman, How to recycle random bits, in FOCS 89.
M. Naor and M. Yung, Public-Key Crypto systems Provably Secure against Chosen Ciphertext Attack, in STOC 90.
T. Okamoto, On Relationships Between Statistical Zero-Knowledge Proofs, in STOC 96.
R. Ostrovsky and A. Wigderson, One-way Functions are Essential for Non-Trivial Zero-Knowledge, in ISTCS 93.
A. Sahai and S. Vadhan, A Complete Promise Problem for Statistical Zero-Knowledge, in FOCS 97.
M. Sipser, A Complexity Theoretic Approach to Randomness, in STOC 83.
A. Shamir, IP=PSPACE, in FOCS 90.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M. (1998). Image density is complete for non-interactive-SZK. In: Larsen, K.G., Skyum, S., Winskel, G. (eds) Automata, Languages and Programming. ICALP 1998. Lecture Notes in Computer Science, vol 1443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055102
Download citation
DOI: https://doi.org/10.1007/BFb0055102
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64781-2
Online ISBN: 978-3-540-68681-1
eBook Packages: Springer Book Archive