The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
The knowledge complexity of interactive proof-systems
Open accessAbstract
How much knowledge should be communicated fir proving a theorem T?Certainly enough to see that T is true, but usually much more.For instance, to prove that a graph is Hamiltonian it suffices to exhibit an Hamiltonian tour.This appears, however, to contain ,much additional knowledge than the single bit "HamiltonianInon-Hamiltonian".We give a computational complexity measure of knowledge and measure tic amount of additional knowlcdgc contained in proofs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
Some complexity questions related to distributive computing(Preliminary Report)
Yao, A. C.-C. (1979) · Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 · doi:10.1145/800135.804414 · Cited by 1,042
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Papadimitriou, C. H. (1985) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(85)90045-5 · Cited by 250
A logic to reason about likelihood
Halpern, J. Y., & Rabin, M. O. (1983) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800061.808760 · Cited by 33
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
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-citationA Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,804
Self-citationEfficient signature generation by smart cards
Schnorr, C. P. (1991) · Journal of Cryptology · doi:10.1007/bf00196725 · Cited by 2,787
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62213 · Cited by 2,524
Security Arguments for Digital Signatures and Blind Signatures
Pointcheval, D., & Stern, J. (2000) · Journal of Cryptology · doi:10.1007/s001450010003 · Cited by 2,209
Efficient Identification and Signatures for Smart Cards
Schnorr, C. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_22 · Cited by 1,381
An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation
Camenisch, J., & Lysyanskaya, A. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_7 · Cited by 1,321
Untraceable Electronic Cash: (Extended Abstract)
Chaum, D., Fiat, A., & Naor, M. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34799-2_25 · Cited by 1,120
Security Proofs for Signature Schemes
Pointcheval, D., & Stern, J. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_33 · Cited by 1,077
Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack
Rackoff, C., & Simon, D. R. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_35 · Cited by 1,039
Self-citationZero-knowledge proofs of identity
Feige, U., Fiat, A., & Shamir, A. (1988) · Journal of Cryptology · doi:10.1007/bf02351717 · Cited by 1,029
Founding crytpography on oblivious transfer
Kilian, J. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62215 · Cited by 1,018
Functional Encryption: Definitions and Challenges
Boneh, D., Sahai, A., & Waters, B. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19571-6_16 · Cited by 1,010
Universal one-way hash functions and their cryptographic applications
Naor, M., & Yung, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73011 · Cited by 959
Minimum disclosure proofs of knowledge
Brassard, G., Chaum, D., & Crépeau, C. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90005-0 · Cited by 959
Security and Privacy on Blockchain
Zhang, R., Xue, R., & Liu, L. (2020) · ACM Computing Surveys · doi:10.1145/3316481 · Cited by 959
Belief, awareness, and limited reasoning
Fagin, R., & Halpern, J. Y. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90003-8 · Cited by 885
SIA: secure information aggregation in sensor networks
Przydatek, B., Song, D., & Perrig, A. (2003) · Proceedings of the 1st international conference on Embedded networked sensor systems · doi:10.1145/958491.958521 · Cited by 789
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Verifiable secret sharing and achieving simultaneity in the presence of faults
Chor, B., Goldwasser, S., Micali, S., & Awerbuch, B. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.64 · Cited by 771
Self-citationShamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103428 · Cited by 616
Definitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
Publicly Verifiable Secret Sharing
Stadler, M. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_17 · Cited by 531
Reasoning about knowledge and probability
Fagin, R., & Halpern, J. Y. (1994) · Journal of the ACM · doi:10.1145/174652.174658 · Cited by 477
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
Self-citationHow to withstand mobile virus attacks (extended abstract)
Ostrovsky, R., & Yung, M. (1991) · Proceedings of the tenth annual ACM symposium on Principles of distributed computing - PODC '91 · doi:10.1145/112600.112605 · Cited by 465
Separating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993651 · Cited by 456
A “Paradoxical” Indentity-Based Signature Scheme Resulting from Zero-Knowledge
Guillou, L. C., & Quisquater, J.-J. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34799-2_16 · Cited by 451
Receipt-free secret-ballot elections (extended abstract)
Benaloh, J., & Tuinstra, D. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195407 · Cited by 432
A robust and verifiable cryptographically secure election scheme
Cohen, J. D., & Fischer, M. J. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.2 · Cited by 408
Zero knowledge proofs of identity
Fiege, U., Fiat, A., & Shamir, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28419 · Cited by 407
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
A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications
Bresson, E., Catalano, D., & Pointcheval, D. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-40061-5_3 · Cited by 355
A new identification scheme based on syndrome decoding
Stern, J. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_2 · Cited by 353
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
Ames, S., Hazay, C., Ishai, Y., & Venkitasubramaniam, M. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134104 · Cited by 305
All-or-Nothing Disclosure of Secrets
Brassard, G., Crepeau, C., & Robert, J.-M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_17 · Cited by 297
Desmedt, Y. G. (1994) · European Transactions on Telecommunications · doi:10.1002/ett.4460050407 · Cited by 292
Attribute-based signature and its applications
Li, J., Au, M. H., Susilo, W., Xie, D., & Ren, K. (2010) · Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security · doi:10.1145/1755688.1755697 · Cited by 279
Goldman, S. A., & Kearns, M. J. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1003 · Cited by 257
Vulnerabilities in federated learning
Bouacida, N., & Mohapatra, P. (2021) · IEEE Access · doi:10.1109/access.2021.3075203 · Cited by 248
On the Design of a Blockchain Platform for Clinical Trial and Precision Medicine
Shae, Z., & Tsai, J. J. P. (2017) · 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2017.61 · Cited by 233
Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]
Goldwasser, S., Kim, M. P., Vaikuntanathan, V., & Zamir, O. (2022) · 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs54457.2022.00092 · Cited by 41
Self-citationData privacy in the age of personal genomics
Grishin, D., Obbad, K., & Church, G. M. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0271-3 · Cited by 38
Regulatory options for integrating zero-knowledge proofs into the European Digital Identity Wallet
Ramos Fernández, R. (2025) · International Review of Law, Computers & Technology · doi:10.1080/13600869.2024.2398915 · Cited by 4
“Zero-knowledge proofs convey no additional knowledge other than the correctness of the proposition in question (Goldwasser, Micali, and Rackoff 1985).”
Models That Prove Their Own Correctness
Amit, N., Goldwasser, S., Paradise, O., & Rothblum, G. (2024) · arXiv · doi:10.48550/arxiv.2405.15722
Self-citation
Metadata
- Authors
- Goldwasser, S., Micali, S., & Rackoff, C.
- Venue
- Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85
- Publisher
- ACM Press
- Published
- 1985
- Pages
- 291-304
- OpenAlex
- W2144752539
- Cited by
- 1,302
- References
- 6
- FWCI
- 22.62
- Type
- conference paper
- Language
- en
- Open access
- gold
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.