Article

How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge

Author:

Lior MalkaAuthors Info & Claims

TCC'08: Proceedings of the 5th conference on Theory of cryptography

Pages 89 - 106

Published: 19 March 2008 Publication History

Abstract

We study perfect zero-knowledge proofs (PZK). Unlike statistical zero-knowledge, where many fundamental questions have been answered, virtually nothing is known about these proofs.

We consider reductions that yield hard and complete problems in the statistical setting. The issue with these reductions is that they introduce errors into the simulation, and therefore they do not yield analogous problems in the perfect setting. We overcome this issue using an error shifting technique. This technique allows us to remove the error from the simulation. Consequently, we obtain the first complete problem for the class of problems possessing non-interactive perfect zero-knowledge proofs (NIPZK), and the first hard problem for the class of problems possessing public-coin PZK proofs.

We get the following applications. Using the error shifting technique, we show that the notion of zero-knowledge where the simulator is allowed to fail is equivalent to the one where it is not allowed to fail. Using our complete problem, we show that under certain restrictions NIPZK is closed under the OR operator. Using our hard problem, we show how a constant-round, perfectly hiding instance-dependent commitment may be obtained (this would collapse the round complexity of public-coin PZK proofs to a constant).

References

[1]

Aiello,W., Håstad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. of Computer and System Sciences 42(3), 327-345 (1991).

Digital Library

[2]

Babai, L., Moran, S.: Arthur-merlin games: A randomized proof system and a hierarchy of complexity classes. J. of Computer and System Sciences 36, 254-276 (1988).

Digital Library

[3]

Bellare, M., Rogaway, P.: Noninteractive perfect zero-knowledge. Unpublished manuscript (June 1990).

[4]

Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the ICM, pp. 1444-1451 (1986).

[5]

Blum, M., Feldman, P.,Micali, S.: Non-interactive zero-knowledge proofs and their applications. In: Proceedings of the 20th STOC, ACM, New York (1988).

Digital Library

[6]

Blum, M., Santis, A.D., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084-1118 (1991).

Digital Library

[7]

Brassard, G., Crépeau, C., Yung, M.: Everything in NP can be argued in perfect zeroknowledge in a bounded number of rounds (extended abstract). In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 192-195. Springer, Heidelberg (1990).

Digital Library

[8]

Damgård, I.: Interactive hashing can simplify zero-knowledge protocol design without computational assumptions (extended abstract). In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 100-109. Springer, Heidelberg (1999).

Digital Library

[9]

Damgård, I., Wigderson, O.G.A.: Hashing functions can simplify zeroknowledge protocol design (too). Technical Report RS-94-39, BRICS (November 1994).

[10]

Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control 61(2), 159-173 (1984).

Digital Library

[11]

Fortnow, L.: The complexity of perfect zero-knowledge. In: Micali, S. (ed.) Advances in Computing Research, vol. 5, pp. 327-343. JAC Press, Inc (1989).

Digital Library

[12]

Goldreich, O.: Foundations of Cryptography, vol. 1. Cambridge University Press, Cambridge (2001).

Digital Library

[13]

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691-729 (1991).

Digital Library

[14]

Goldreich, O., Sahai, A., Vadhan, S.P.:Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: STOC, pp. 399-408 (1998).

Digital Library

[15]

Goldreich, O., Sahai, A., Vadhan, S.P.: Can statistical zero knowledge be made noninteractive? or on the relationship of SZK and NISZK. In:Wiener,M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, Springer, Heidelberg (1999).

Digital Library

[16]

Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In: IEEE Conference on Computational Complexity, pp. 54-73 (1999).

Digital Library

[17]

Goldwasser, S., Sipser, M.: Private-coins versus public-coins in interactive proof systems. In: Micali, S. (ed.) Advances in Computing Research, vol. 5, pp. 73-90. JAC Press, Inc (1989).

[18]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186-208 (1989).

Digital Library

[19]

Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339-358. Springer, Heidelberg (2006).

Digital Library

[20]

Itoh, T., Ohta, Y., Shizuya, H.: A language-dependent cryptographic primitive. J. Cryptology 10(1), 37-50 (1997).

Digital Library

[21]

Kapron, B., Malka, L., Srinivasan, V.: Characterizing non-interactive instance-dependent commitment-schemes (NIC). In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 328-339. Springer, Heidelberg (2007).

Digital Library

[22]

Nguyen, M.-H., Ong, S.J., Vadhan, S.: Statistical zero-knowledge arguments for NP from any one-way function. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, CA, October 2006, pp. 3-14 (2006).

Digital Library

[23]

Nguyen, M.-H., Vadhan, S.: Zero knowledge with efficient provers. In: STOC 2006: Proceedings of the thirty-eighth annual ACMsymposium on Theory of computing, pp. 287-295. ACM Press, New York, USA (2006).

Digital Library

[24]

Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47-108 (2000).

Digital Library

[25]

Petrank, E., Tardos, G.: On the knowledge complexity of NP. In: FOCS, pp. 494-503 (1996).

Digital Library

[26]

Sahai, A., Vadhan, S.P.: A complete problem for statistical zero-knowledge. J. ACM 50(2), 196-249 (2003).

Digital Library

[27]

De Santis, A., Di Crescenzo, G., Persiano, G.: The knowledge complexity of quadratic residuosity languages. Theor. Comput. Sci. 132(1-2), 291-317 (1994).

Digital Library

[28]

De Santis, A., Di Crescenzo, G., Persiano, G.: Randomness-efficient non-interactive zeroknowledge (extended abstract). In: Automata, Languages and Programming, pp. 716-726 (1997).

Digital Library

[29]

De Santis, A., Di Crescenzo, G., Persiano, G.: On NC<sup>1</sup> boolean circuitcomposition of noninteractive perfect zero-knowledge. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 356-367. Springer, Heidelberg (2004).

[30]

De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: Image densityis complete for noninteractive-SZK (extended abstract). In: Larsen, K.G., Skyum, S.,Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 784-795. Springer, Heidelberg (1998).

Digital Library

[31]

Tompa, M., Woll, H.: Random self-reducibility and zero-knowledge interactive proofs of possession of information. In: 28th FOCS, pp. 472-482 (1987).

Digital Library

[32]

Vadhan, S.P.: A study of statistical zero-knowledge proofs. PhD thesis, MIT (1999).

Digital Library

[33]

Vadhan, S.P.: An unconditional study of computational zero knowledge. In: FOCS, pp. 176- 185 (2004).

Digital Library

Cited By

Yan J(2012)Complete problem for perfect zero-knowledge quantum proofProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_34(419-430)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_34

Recommendations

How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge

This paper studies perfect zero-knowledge proofs. Such proofs do not allow any simulation errors, and therefore techniques from the study of statistical zero-knowledge (where a small error is allowed) do not apply to them. We introduce a new error ...
A study of perfect zero-knowledge proofs
Complete problem for perfect zero-knowledge quantum proof
SOFSEM'12: Proceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science

The main purpose of this paper is to prove that (promise) problem Quantum State Identicalness (abbreviated QSI) is <em>essentially</em> complete for perfect zero-knowledge quantum interactive proof (QPZK). Loosely speaking, problem QSI is to decide ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'08: Proceedings of the 5th conference on Theory of cryptography

March 2008

644 pages

ISBN:354078523X

Editor:
Ran Canetti
IBM T.J. Watson Research Center, NY

Sponsors

Microsoft Inc.
IBM Inc.
The D. E. Shaw group
IACR: International Association for Cryptologic Research

In-Cooperation

New York University
Courant Institute for Mathematical Sciences

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 19 March 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yan J(2012)Complete problem for perfect zero-knowledge quantum proofProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_34(419-430)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_34

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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents