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
Items 101–140 of 140
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100225 · Cited by 303
An Identity-Based Key-Exchange Protocol
Günther, C. G. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46885-4_5 · Cited by 299
Efficient Concurrent Zero-Knowledge in the Auxiliary String Model
Damgård, I. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45539-6_30 · Cited by 295
Micali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
Self-citationRobust Non-interactive Zero Knowledge
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., & Sahai, A. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_33 · Cited by 293
Privacy in the Smart City—Applications, Technologies, Challenges, and Solutions
Eckhoff, D., & Wagner, I. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2748998 · Cited by 287
Designing programs that check their work
Blum, M., & Kanna, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73015 · Cited by 287
Anonymous Identification in Ad Hoc Groups
Dodis, Y., Kiayias, A., Nicolosi, A., & Shoup, V. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_36 · Cited by 284
Designing confidentiality-preserving Blockchain-based transaction processing systems
Wang, Y., & Kogan, A. (2018) · International Journal of Accounting Information Systems · doi:10.1016/j.accinf.2018.06.001 · Cited by 282
Non-interactive cryptocomputing for NC/sup 1/
Sander, T., Young, A., & Yung, M. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814630 · Cited by 279
Foundations of Secure Interactive Computing
Beaver, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_31 · Cited by 277
Composition and integrity preservation of secure reactive systems
Pfitzmann, B., & Waidner, M. (2000) · Proceedings of the 7th ACM conference on Computer and Communications Security · doi:10.1145/352600.352639 · Cited by 277
Probabilistic checking of proofs; a new characterization of NP
Arora, S., & Safra, S. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267824 · Cited by 275
Succinct Non-interactive Arguments via Linear Interactive Proofs
Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., & Ostrovsky, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_18 · Cited by 274
Ferrag, M. A., Maglaras, L., Argyriou, A., Kosmanos, D., & Janicke, H. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2017.10.017 · Cited by 274
A Survey on Anonymity and Privacy in Bitcoin-Like Digital Cash Systems
Kus Khalilov, M. C., & Levi, A. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2818623 · Cited by 271
Introduction to Property Testing
Goldreich, O. (2017) · Cambridge University Press eBooks · doi:10.1017/9781108135252 · Cited by 270
Randomizable Proofs and Delegatable Anonymous Credentials
Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., & Shacham, H. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_7 · Cited by 269
Formal certification of code-based cryptographic proofs
Barthe, G., Grégoire, B., & Zanella Béguelin, S. (2009) · Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1480881.1480894 · Cited by 268
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 265
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Doubly-Efficient zkSNARKs Without Trusted Setup
Wahby, R. S., Tzialla, I., Shelat, A., Thaler, J., & Walfish, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00060 · Cited by 276
Dwork, C., & Naor, M. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892117 · Cited by 264
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2016) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2512870 · Cited by 257
Optimal algorithms for Byzantine agreement
Feldman, P., & Micali, S. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62225 · Cited by 255
Self-citationProactive public key and signature systems
Herzberg, A., Jakobsson, M., Jarecki, S., Krawczyk, H., & Yung, M. (1997) · Proceedings of the 4th ACM conference on Computer and communications security · doi:10.1145/266420.266442 · Cited by 253
Vulnerabilities in federated learning
Bouacida, N., & Mohapatra, P. (2021) · IEEE Access · doi:10.1109/access.2021.3075203 · Cited by 248
Quantum computation vs. firewalls
Harlow, D., & Hayden, P. (2013) · Journal of High Energy Physics · doi:10.1007/jhep06(2013)085 · Cited by 310
“Even for fixed k, however, the decoding problem is almost certainly at least QSZK-hard and there are strong reasons to believe that such problems can’t be solved in polynomial time on a quantum computer.”
BackgroundInfluentialParno (2016) · doi:10.1145/2856449 · Cited by 212
“Finally, the theory community has produced a number of beautiful, general-purpose protocols [16–23] that offer compelling asymptotics.”
BackgroundA Survey of Self-Sovereign Identity Ecosystem
Soltani, R., Nguyen, U. T., & An, A. (2021) · Security and Communication Networks · doi:10.1155/2021/8873429 · Cited by 131
Security Aspects of Blockchain Technology Intended for Industrial Applications
Idrees, S. M., Nowostawski, M., Jameel, R., & Mourya, A. K. (2021) · Electronics · doi:10.3390/electronics10080951 · Cited by 127
“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].”
BackgroundA taxonomic approach to understanding emerging blockchain identity management systems
Lesavre, L. (2020) · doi:10.6028/nist.cswp.01142020 · Cited by 64
Sim: a utility for detecting similarity in computer programs
Gitchell, D., & Tran, N. (1999) · ACM SIGCSE Bulletin · doi:10.1145/384266.299783 · Cited by 62
Zero trust: Never trust, always verify
Wylde, A. (2021) · 2021 International Conference on Cyber Situational Awareness, Data Analytics and Assessment (CyberSA) · doi:10.1109/cybersa52016.2021.9478244 · Cited by 62
“Prominent approaches that overcome these limitations (when we do not trust anyone), include zero knowledge proofs [14] and garbled circuits [15], briefly discussed next.”
BackgroundMethodInfluentialPrivacy-Enhancing Technologies in Federated Learning for the Internet of Healthcare Things: A Survey
Mosaiyebzadeh, F., Pouriyeh, S., Parizi, R. M., Sheng, Q. Z., Han, M., Zhao, L., Sannino, G., Ranieri, C. M., Ueyama, J., & Batista, D. M. (2023) · Electronics · doi:10.3390/electronics12122703 · Cited by 51
A Taxonomic Approach to Understanding Emerging Blockchain Identity Management Systems
(2020) · doi:10.6028/nist.cswp.9 · Cited by 36
Formalizing Data Deletion in the Context of the Right to Be Forgotten
Garg, S., Goldwasser, S., & Vasudevan, P. N. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45724-2_13 · Cited by 8
Self-citationOpen Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents
de Witt, C. S., Krawiecka, K., Krawczuk, I., Hagag, B., Anderson, W. L., Belcak, P., Bucknall, B., Cai, X., Chopra, A., Cohen, D., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.02077 · Cited by 108
“…interaction protocols and environments - drawing inspiration from secure multi-party computation, verifiable interactions (Goldreich et al., 1987b; Goldwasser et al., 1989; Hammond & Adam-Day, 2025b), and incentive design (Nisan & Ronen, 2001) - that facilitate beneficial collaboration among…”
Cqrs and blockchain with zero-knowledge proofs for secure multi-agent decision-making
CHERIF, A. N., YOUSSFI, M., EN-NAIMANI, Z., TADLAOUI, A., SOULAMI, M., & BOUATTANE, O. (2024) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2024.0151188 · Cited by 1
AZR: Risk-Adaptive Verification for Decentralized AI Inference on Blockchain Rollups
Virani, A. (2026) · Zenodo · doi:10.5281/zenodo.20703363
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
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.