The Knowledge Complexity of Interactive Proof Systems
The DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Abstract
Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that a graph is Hamiltonian it suffices to exhibit a Hamiltonian tour in it; however, this seems to contain more knowledge than the single bit Hamiltonian/non-Hamiltonian.In this paper a computational complexity theory of the “knowledge” contained in a proof is developed. Zero-knowledge proofs are defined as those proofs that convey no additional knowledge other than the correctness of the proposition in question. Examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity. These are the first examples of zero-knowledge proofs for languages not known to be efficiently recognizable.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Currently proposed algorithms include trees [118], linear and logistic regression [490, 224, 316], and neural networks [317].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [317]
In the citing paper
“After 27 years from the time the paper was published, Goldwasser et al. won the Turing award for their effort in ZKP.”
From A Survey of Self-Sovereign Identity Ecosystem (2021) · cites this paper as [126]
In the citing paper
“Zero Knowledge Proofs were first published by Goldwasser et al. in 1985 [126].”
From A Survey of Self-Sovereign Identity Ecosystem (2021) · cites this paper as [126]
In the citing paper
“Furthermore, bidding and contracts are also an aspect of the business domain that needs to be secured and transparent, which can be implemented using blockchain, which would eliminate third party/human involvement, hence reducing the chances of any discrepancy or unnecessary costs [144,145].”
From Security Aspects of Blockchain Technology Intended for Industrial Applications (2021) · cites this paper as [144]
Citations
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Self-citationGoldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Self-citationChandra, A. K., Kozen, D. C., & Stockmeyer, L. J. (1981) · Journal of the ACM · doi:10.1145/322234.322243 · Cited by 1,221
Theory and application of trapdoor functions
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.45 · Cited by 968
The relative efficiency of propositional proof systems
Cook, S. A., & Reckhow, R. A. (1979) · Journal of Symbolic Logic · doi:10.2307/2273702 · Cited by 831
Does co-NP have short interactive proofs?
Boppana, R. B., Hastad, J., & Zachos, S. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90232-8 · Cited by 363
Papadimitriou, C. H. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.20 · Cited by 50
A Secure Protocol for the Oblivious Transfer (Extended Abstract)
Fischer, M. J., Micali, S. M., & Rackoff, C. (1996) · Journal of Cryptology · doi:10.1007/bf00208002 · Cited by 28
Self-citationA Secure Protocol for the Oblivious Transfer (Extended Abstract)
Fischer, M. J., Micali, S., & Rackoff, C. (1996) · Journal of Cryptology · doi:10.1007/s001459900011 · Cited by 15
Self-citation
Research works printed but not linked: 24
- B. Aiello, S. Goldwasser, J. Hastad, On the power of interaction, Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 368–379 · doi:10.1109/sfcs.1986.36
- B. Aiello, J. Hastad, Perfect zero-knowledge languages can be recognized in two rounds, Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, 439–448 · doi:10.1109/sfcs.1987.47
- M. Ben-Or, O. Golureich, S. Goldwasser, J. Hastad, J. Kilian, P. Rogaway, S. Micali, Everything provable is provable in zero-knowledge, in Proc. Crypto88, to appear
- Blum M., 1982, IEEE COMPCON, 133
- L. Babai, Trading group theory for randomness, Proc.17th ACM Annual Symposium on Theory of Computation, 1975, 421–429 · DOI · Paper page
- L. Babai, S. Moran, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, 421–429, J. Comput. Sci. Systems; a previous version was entitled Trading group theory for randomness · DOI · Paper page
- L. Babai, E. Szemeredi, On the complexity of matrix group problems, Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 229–240 · DOI · Paper page
- G. Brassard, C. Crepau, Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond, Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, October · doi:10.1109/sfcs.1986.33
- D. Chaum, Demonstrating the public predicate can be satisfied without revealing any information how, in Proc. Crypto86
- J. Cohen (Benaloh), Cryptographic capsules, in Proc. Crypto86
- U. Feige, A. Fiat, A. Shamir, Zero knowledge proofs of identity, Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, 210–217 · DOI · Paper page
- L. Fortnow, The complexity of perfect zero-knowledge, Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, 204–209 · DOI · Paper page
- R. Fagin, J. Halpern, Belief, awareness, and limited reasoning, Proc. 9th International Joint Conference on Artificial Intelligence, 1985, 491–501
- R. Fagin, J. Halpern, M. Vardi, A model theoretic analysis of knowledge, Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, 268–278 · doi:10.1109/sfcs.1984.715925
- O. Goldreich, Y. Mansour, M. Sipser, Interactive proof systems: Provers that never fail and random selection, Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, 449–460 · doi:10.1109/sfcs.1987.35
- S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems, 1985, in Proc. 27th Annual Symposium on Foundations of Computer Science, pp. 291-304. Earlier version: Knowledge complexity, unpublished manuscript, (submitted to FOCS, 1984) · DOI · Paper page
- S. Goldwasser, M. Sipser, Private coins versus public coins in interactive proof systems, Proc. 18th Annual Symposium on Theory of Computing, 1986, 59–68 · DOI · Paper page
- Z. Galil, S. Haber, M. Yung, A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems, Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, 360–371 · DOI
- O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 174–187 · DOI · Paper page
- J. Halpern, Y. Moses, Knowledge and common knowledge in a distributed environment, Proc. 3rd Principles of Distributed Computing Conference, 1984, 50–61 · doi:10.1145/800222.806735
- M. Luby, S. Micali, C. Rackoff, How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin, Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, 11–22 · doi:10.1109/sfcs.1983.25
- Y. Oren, On the cunning power of cheating verifiers: some observations of zero-knowledge proofs, Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, 462–471 · DOI
- M. Tompa, H. Woll, Random self reducibility and zero knowledge interactive proofs of possession of information, Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, 472–482 · DOI · Paper page
- S. Zachos, M. Furer, Probabilistic quantifiers vs. distrustful adversaries, Proc. Structure of Complexity Classes Conference, 1986 · DOI
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“t depend on secret information known to the prover, called witness, without revealing those secrets to the verifier. The notion of zero-knowledge was introduced in the late 1980’s by Goldwasser et al. [184]. It provides a solution for the verifiability question on private data. While there had been a large body of work…”
BackgroundRandom oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
Universally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
Gühne, O., & Tóth, G. (2009) · Physics Reports · doi:10.1016/j.physrep.2009.02.004 · Cited by 2,401
Metadata
- Authors
- Goldwasser, S., Micali, S., & Rackoff, C.
- Affiliations
- Massachusetts Institute of Technology (US)
- University of Toronto (CA)
- ORCID
- Goldwasser, Shafi
- Venue
- SIAM Journal on Computing
- Published
- 1989-02
- Volume
- 18
- Issue
- 1
- Pages
- 186-208
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1970606468
- Cited by
- 3,285
- References
- 10
- Citations by year
- 2026: 102 · 2025: 122 · 2024: 115 · 2023: 122 · 2022: 130 · 2021: 188 · 2020: 169 · 2019: 142 · 2018: 91 · 2017: 78 · 2016: 91 · 2015: 115 · 2014: 109 · 2013: 124 · 2012: 122
- FWCI
- 44.38
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- interactive proofs, zero-knowledge proofs, knowledge complexity, quadratic residuosity, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Knowledge Complexity of Interactive Proof Systems. https://app.cochat.ai/papers/10.1137/0218012
- The paper
- Goldwasser, S., Micali, S., & Rackoff, C. (1989). The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing. https://doi.org/10.1137/0218012
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.