CoChat

The Knowledge Complexity of Interactive Proof Systems

Goldwasser, Shafi, Micali, Silvio, Rackoff, Charles · 1989 · SIAM Journal on Computing

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

Crossref · 10.1137/0218012

Cites

10 of 10 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Show all 10 references

Research works printed but not linked: 24

  1. 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
  2. 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
  3. 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
  4. Blum M., 1982, IEEE COMPCON, 133
  5. L. Babai, Trading group theory for randomness, Proc.17th ACM Annual Symposium on Theory of Computation, 1975, 421–429 · DOI · Paper page
  6. 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
  7. 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
  8. 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
  9. D. Chaum, Demonstrating the public predicate can be satisfied without revealing any information how, in Proc. Crypto86
  10. J. Cohen (Benaloh), Cryptographic capsules, in Proc. Crypto86
  11. 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
  12. L. Fortnow, The complexity of perfect zero-knowledge, Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, 204–209 · DOI · Paper page
  13. R. Fagin, J. Halpern, Belief, awareness, and limited reasoning, Proc. 9th International Joint Conference on Artificial Intelligence, 1985, 491–501
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. S. Zachos, M. Furer, Probabilistic quantifiers vs. distrustful adversaries, Proc. Structure of Complexity Classes Conference, 1986 · DOI

Cited by

Metadata

Authors
Goldwasser, S., Micali, S., & Rackoff, C.
Affiliations
  • Massachusetts Institute of Technology (US)
  • University of Toronto (CA)
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

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.