Abstract
The notion of a “proof of knowledge,” suggested by Goldwasser, Micali and Rackoff, has been used in many works as a tool for the construction of cryptographic protocols and other schemes. Yet the commonly cited formalizations of this notion are unsatisfactory and in particular inadequate for some of the applications in which they are used. Consequently, new researchers keep getting misled by existing literature. The purpose of this paper is to indicate the source of these problems and suggest a definition which resolves them.
Research was partially supported by grant No. 89-00312 from the US-Israel Binational Science Foundation (BSF), Jerusalem, Israel.
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
D. Beaver, and J. Feigenbaum, “Hiding Instances in Multioracle Queries,” Proc. of the 7th STACS, 1990, pp. 37–48.
M. Bellare, S. Micali and R. Ostrovsky, “The True Complexity of Statistical Zero-Knowledge,” Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, ACM (1990), pp. 494–502.
G. Brassard, D. Chaum, and C. Crépeau, “Minimum Disclosure Proofs of knowledge,” JCSS, Vol. 37, No. 2, 1988, pp. 156–189.
J. Boyar, C. Lund and R. Peralta, “On the Communication Complexity of Zero-Knowledge Proofs.” 1989.
G. Brassard, C. Crépeau, S. Laplante and C. Léger, “Computationally Convincing Proofs of Knowledge,” Proc. of the 8th STACS, 1991.
U. Feige, A. Fiat, and A. Shamir, “Zero-Knowledge Proofs of Identity”, Journal of Cryptology, Vol. 1, 1988, pp. 77–94.
U. Feige, and A. Shamir, “Witness Indistinguishability and Witness Hiding Protocols,” Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, ACM (1990), pp 416–426.
Z. Galil, S. Haber, and M. Yung, “Symmetric Public-Key Encryption”, Advances in Cryptology — Crypto85 proceedings, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, 1986, pp. 128–137.
M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos, “On Completeness and Soundness in Interactive Proof Systems”, Advances in Computing Research: a research annual, Vol. 5 (S. Micali, ed.), pp. 429–442, 1989.
O. Goldreich, “A Uniform-Complexity Treatment of Encryption and Zero-Knowledge”, J. of Cryptology, to appear.
O. Goldreich, and H. Krawczyk, “On Sequential and Parallel Composition of Zero-Knowledge Protocols”, 17th ICALP, Lecture Notes in Computer Science, Vol. 443, Springer-Verlag, 1990, pp. 268–282.
O. Goldreich, S. Micali, and A. Wigderson, “Proofs that Yields Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems”, JACM, Vol. 38, No. 1, July 1991.
O. Goldreich, and Y. Oren, “Definitions and Properties of Zero-Knowledge Proof Systems”, TR-610, Computer Science Dept., Technion, Haifa, Israel. Submitted to Jour of Cryptology.
S. Goldwasser, S. Micali, and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems”, SIAM J. on Computing, Vol. 18, No. 1, 1989, pp. 186–208.
S. Haber, “Multi-Party Cryptographic Computations: Techniques and Applications”, PhD Dissertation, Computer Science Dept., Columbia University, Nov. 1987.
Y. Oren, “On the Cunning Power of Cheating Verifiers: Some Observations about Zero-Knowledge Proofs,” Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1987), pp. 462–471.
A. Shamir, “IP=PSPACE,” Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1990), pp. 11–15.
M. Tompa and H. Woll, “Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information,” University of California (San Diego) Computer Science and Engineering Dept. Technical Report Number CS92-244 (June 1992). (Preliminary version in Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1987), pp. 472–482.)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Goldreich, O. (1993). On Defining Proofs of Knowledge. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_28
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive