The Knowledge Complexity of Interactive Proof Systems
E17288
"The Knowledge Complexity of Interactive Proof Systems" is a seminal theoretical computer science paper that introduced the notion of zero-knowledge proofs, fundamentally shaping modern cryptography and complexity theory.
Aliases (2)
- Interactive proof systems and zero-knowledge ×1
- The knowledge complexity of interactive proof systems ×1
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
scientific paper
→
theoretical computer science paper → |
| assumes |
existence of one-way functions
→
existence of pseudorandom generators → |
| author |
Charles Rackoff
→
Shafi Goldwasser → Silvio Micali → |
| citationStatus |
highly cited
→
|
| coauthorRelationship |
collaboration between Goldwasser, Micali, and Rackoff
→
|
| coreConcept |
completeness
→
probabilistic polynomial-time verifier → prover-verifier interaction → simulation paradigm → simulator for verifier’s view → soundness → |
| defines |
computational zero-knowledge
→
knowledge complexity of a proof system → perfect zero-knowledge → statistical zero-knowledge → zero-knowledge interactive proof → |
| field |
computational complexity theory
→
cryptography → theoretical computer science → |
| hasAuthorAffiliationAtTimeOfPublication |
Massachusetts Institute of Technology
→
|
| impact |
basis for many cryptographic protocols
→
foundation of zero-knowledge proof theory → |
| influencedField |
complexity theory
→
modern cryptography → secure protocols → |
| introducedConcept |
knowledge complexity
→
zero-knowledge proof → |
| language |
English
→
|
| publicationYear |
1985
→
|
| publishedIn |
Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing
→
|
| publisher |
Association for Computing Machinery
→
|
| recognizedAs |
seminal paper in complexity theory
→
seminal paper in cryptography → |
| resultType |
theoretical result
→
|
| shows |
existence of zero-knowledge proofs for some NP problems under cryptographic assumptions
→
|
| studies |
information revealed by proofs
→
interactive proof systems → |
| subfield |
interactive proof systems
→
zero-knowledge proofs → |
| topic |
computational security
→
information-theoretic security → interactive proofs → zero-knowledge proofs → |
Referenced by (3)
| Subject (surface form when different) | Predicate |
|---|---|
|
Charles Rackoff
("The knowledge complexity of interactive proof systems")
→
Charles Rackoff ("Interactive proof systems and zero-knowledge") → Shafi Goldwasser → |
notableWork |