Abstract
We extend the study of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of problems possessing interactive statistical zero-knowledge proofs. Along these lines, we first show that if statistical zero knowledge is non-trivial then so is non-interactive statistical zero knowledge, where by non-trivial we mean that the class includes problems which are not solvable in probabilistic polynomial-time. (The hypothesis holds under various assumptions, such as the intractability of the Discrete Logarithm Problem.) Furthermore, we show that if NISZK is closed under complement, then in fact SZK = NISZK, i.e. all statistical zero-knowledge proofs can be made non-interactive.
The main tools in our analysis are two promise problems that are natural restrictions of promise problems known to be complete for SZK. We show that these restricted problems are in fact complete for NISZK and use this relationship to derive our results comparing the two classes. The two problems refer to the statistical difference, and difference in entropy, respectively, of a given distribution from the uniform one. We also consider a weak form of NISZK, in which only requires that for every inverse polynomial 1=p(n), there exists a simulator which achieves simulator deviation 1=p(n), and show that this weak form of NISZK actually equals NISZK.
The full version of this paper has been submitted to the Electronic Colloquium on Computational Complexity [26].
Chapter PDF
Similar content being viewed by others
References
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the Thirty Third Annual Symposium on Foundations of Computer Science, pages 14–23, 1992.
Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs. In Proceedings of the Thirty Third Annual Symposium on Foundations of Computer Science, pages 2–13, 1992.
Mihir Bellare and Shafi Goldwasser. New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. In G. Brassard, editor, Advances in Cryptology—CRYPTO’ 89, volume 435 of Lecture Notes in Computer Science, pages 194–211. Springer-Verlag, 1990, 20–24 August 1989.
Mihir Bellare, Silvio Micali, and Rafail Ostrovsky. Perfect zero-knowledge in constant rounds. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 482–493, 1990.
Mihir Bellare and Phillip Rogaway. Non-interactive perfect zero-knowledge. Unpublished manuscript, June 1990.
Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084–1118, December 1991.
Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 103–112, Chicago, Illinois, 2–4 May 1988.
Ivan Damgård. Interactive hashing can simplify zero-knowledge protocol design. In Proceedings of Crypto’ 95, Lecture Notes in Computer Science, volume 403, pages 100–109. Springer-Verlag, 1994.
Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, and Avi Wigderson. Honest verifier vs. dishonest verifier in public coin zero-knowledge proofs. In Proceedings of Crypto’ 95, Lecture Notes in Computer Science, volume 403. Springer-Verlag, 1995.
Ivan Damgård, Oded Goldreich, and Avi Wigderson. Hashing functions can simplify zero-knowledge protocol design (too). Technical Report RS-94-39, BRICS, November 1994. See Part 1 of [9].
Alfredo De Santis, Giovanni Di Crescenzo, and Giuseppe Persiano. Randomness-efficient non-interactive zero-knowledge (extended abstract). In Pierpaolo Degano, Robert Gorrieri, and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, 24th International Colloquium, volume 1256 of Lecture Notes in Computer Science, pages 716–726, Bologna, Italy, 7–11 July 1997. Springer-Verlag.
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, and Moti Yung. Image Density is complete for non-interactive-SZK. In Automata, Languages and Programming, 25th International Colloquium, Lectures Notes in Computer Science, pages 784–795, Aalborg, Denmark, 13–17 July 1998. Springer-Verlag. See [13].
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, and Moti Yung. Image Density is complete for non-interactive-SZK, May 1999. Preliminary draft of full version.
Alfredo De Santis, Giovanni Di Crescenzo, and Guiseppe Persiano. The knowledge complexity of quadratic residuosity languages. Theoretical Computer Science, 132(1–2):291–317, 26 September 1994.
Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Non-interactive zero-knowledge proof systems. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO’ 87, volume 293 of Lecture Notes in Computer Science, pages 52–72. Springer-Verlag, 1988, 16–20 August 1987.
Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Non-interactive zero-knowledge with preprocessing. In S. Goldwasser, editor, Advances in Cryptology — CRYPTO’ 88, volume 403 of Lecture Notes in Computer Science, pages 269–282. Springer-Verlag, 1990, 21–25 August 1988.
Giovanni Di Crescenzo, Tatsuaki Okamoto, and Moti Yung. Keeping the SZK-verifier honest unconditionally. In Advances in Cryptology — CRYPTO’ 97, pages 31–45, 1997.
Danny Dolev, Cynthia Dwork, and Moni Naor. Non-malleable cryptography (extended abstract). In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 542–552, New Orleans, Louisiana, 6–8 May 1991.
Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent zero-knowledge. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 409–418, 1998.
Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 308–317, St. Louis, Missouri, 22-24 October 1990. IEEE.
Lance Fortnow. The complexity of perfect zero-knowledge. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 327–343. JAC Press, Inc., 1989.
Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6:97–116, 1993.
Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the Association for Computing Machinery, 38(1):691–729, 1991.
Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, Winter 1994.
Oded Goldreich, Amit Sahai, and Salil Vadhan. Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 399–408, 1998.
Oded Goldreich, Amit Sahai, and Salil Vadhan. Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. Submitted to ECCC, May 1999. http://www.eccc.uni-trier.de/eccc/.
Oded Goldreich and Salil Vadhan. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 54–73, Atlanta, GA, May 1999. IEEE Computer Society Press.
Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, February 1989.
Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pages 12–24, Seattle, Washington, 15-17 May 1989.
Joe Kilian and Erez Petrank. An efficient noninteractive zero-knowledge proof system for NP with general assumptions. Journal of Cryptology, 11(1):1–27, Winter 1998.
R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103–123, December 1975.
Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proofs. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 1–10, 1990.
Moni Naor and Moti Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 427–437, Baltimore, Maryland, 14–16 May 1990.
Tatsuaki Okamoto. On relationships between statistical zero-knowledge proofs. In Proceedings of the Twenty Eighth Annual ACM Symposium on the Theory of Computing, 1996. See also preprint of full version, Oct. 1997.
Rafail Ostrovsky. One-way functions, hard on average problems, and statistical zero-knowledge proofs. In Proceedings of the Thirty Second Annual Symposium on Foundations of Computer Science, pages 133–138, 1991.
Rafail Ostrovsky and Avi Wigderson. One-way functions are essential for nontrivial zero-knowledge. In Proceedings of the Second Israel Symposium on Theory of Computing and Systems, 1993.
Amit Sahai and Salil Vadhan. A complete promise problem for statistical zero-knowledge. In Proceedings of the Thirty Eighth Annual Symposium on Foundations of Computer Science, pages 448–457, 1997.
Amit Sahai and Salil Vadhan. Manipulating statistical difference. In Panos Pardalos, Sanguthevar Rajasekaran, and José Rolim, editors, Randomization Methods in Algorithm Design (DIMACS Workshop, December 1997), volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 251–270. American Mathematical Society, 1999.
Adi Shamir. IP=PSPACE. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 11–15, 1990.
Andrew C. Yao. Theory and application of trapdoor functions. In Proceedings of the Twenty Third Annual Symposium on Foundations of Computer Science, pages 80–91, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldreich, O., Sahai, A., Vadhan, S. (1999). Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK . In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_30
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive