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
Security Arguments for Digital Signatures and Blind Signatures
Pointcheval, D., & Stern, J. (2000) · Journal of Cryptology · doi:10.1007/s001450010003 · Cited by 2,209
Pors: proofs of retrievability for large files
Juels, A., & Kaliski, B. S. (2007) · Proceedings of the 14th ACM conference on Computer and communications security · doi:10.1145/1315245.1315317 · Cited by 1,894
Entity Authentication and Key Distribution
Bellare, M., & Rogaway, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_21 · Cited by 1,752
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels
Canetti, R., & Krawczyk, H. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_28 · Cited by 1,653
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
Divertible protocols and atomic proxy cryptography
Blaze, M., Bleumer, G., & Strauss, M. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054122 · Cited by 1,582
Secure quantum key distribution with realistic devices
Xu, F., Ma, X., Zhang, Q., Lo, H.-K., & Pan, J.-W. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.025002 · Cited by 1,543
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Security and Composition of Multiparty Cryptographic Protocols
Canetti, R. (2000) · Journal of Cryptology · doi:10.1007/s001459910006 · Cited by 1,403
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
Self-citationOn the Size of Pairing-Based Non-interactive Arguments
Groth, J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_11 · Cited by 1,271
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
Cramer, R., Damgård, I., & Schoenmakers, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48658-5_19 · Cited by 1,152
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,145
Desmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_28 · Cited by 1,131
Public-key cryptosystems provably secure against chosen ciphertext attacks
Naor, M., & Yung, M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100273 · Cited by 1,088
Efficient Non-interactive Proof Systems for Bilinear Groups
Groth, J., & Sahai, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_24 · Cited by 1,076
Zero-knowledge proofs of identity
Feige, U., Fiat, A., & Shamir, A. (1988) · Journal of Cryptology · doi:10.1007/bf02351717 · Cited by 1,029
Dolev, D., Dwork, C., & Naor, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103474 · Cited by 990
Security and Privacy on Blockchain
Zhang, R., Xue, R., & Liu, L. (2020) · ACM Computing Surveys · doi:10.1145/3316481 · Cited by 959
Replication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
Non-interactive zero-knowledge and its applications
Blum, M., Feldman, P., & Micali, S. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62222 · Cited by 904
Self-citationPinocchio: Nearly Practical Verifiable Computation
Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.47 · Cited by 864
A guide to completeness and complexity for modal logics of knowledge and belief
Halpern, J. Y., & Moses, Y. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90049-4 · Cited by 845
A secure and efficient conference key distribution system: Extended abstract
Burmester, M., & Desmedt, Y. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053443 · Cited by 844
Raz, R., & Safra, S. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258641 · Cited by 834
Cryptographic distinguishability measures for quantum-mechanical states
Fuchs, C. A., & van de Graaf, J. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.761271 · Cited by 773
Universally Composable Notions of Key Exchange and Secure Channels
Canetti, R., & Krawczyk, H. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-46035-7_22 · Cited by 746
“In addition, it is used for capturing security of tasks such as zero-knowledge [ gmra89 ] and general cryptographic protocols (e.g., [gl90,mr91,b91,c00,psw00,dm00,c01]).”
MethodDolev, D., Dwork, C., & Naor, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795291562 · Cited by 746
Proof verification and hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267823 · Cited by 741
Extracting Training Data from Large Language Models
Carlini, N., Tramer, F., Wallace, E., Jagielski, M., Herbert-Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U., et al. (2020) · arXiv · doi:10.48550/arxiv.2012.07805 · Cited by 727
Pseudo-random generation from one-way functions
Impagliazzo, R., Levin, L. A., & Luby, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73009 · Cited by 724
Universally composable two-party and multi-party secure computation
Canetti, R., Lindell, Y., Ostrovsky, R., & Sahai, A. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509980 · Cited by 717
Micali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Self-citationSelf-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
A Signature Scheme with Efficient Protocols
Camenisch, J., & Lysyanskaya, A. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36413-7_20 · Cited by 662
Universally Composable Commitments
Canetti, R., & Fischlin, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_2 · Cited by 621
Definitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)*
Abadi, M., & Rogaway, P. (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0014-7 · Cited by 613
A note on efficient zero-knowledge proofs and arguments (extended abstract)
Kilian, J. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129782 · Cited by 606
Security and Privacy in Cloud Computing
Xiao, Z., & Xiao, Y. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2012.060912.00182 · Cited by 596
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes
Okamoto, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_3 · Cited by 581
Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security
Sahai, A. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814628 · Cited by 575
Proofs of ownership in remote storage systems
Halevi, S., Harnik, D., Pinkas, B., & Shulman-Peleg, A. (2011) · Proceedings of the 18th ACM conference on Computer and communications security · doi:10.1145/2046707.2046765 · Cited by 562
On Defining Proofs of Knowledge
Bellare, M., & Goldreich, O. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_28 · Cited by 556
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
Adaptively secure multi-party computation
Canetti, R., Feige, U., Goldreich, O., & Naor, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.238015 · Cited by 548
Provably Secure Higher-Order Masking of AES
Rivain, M., & Prouff, E. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15031-9_28 · Cited by 526
Witness indistinguishable and witness hiding protocols
Feige, U., & Shamir, A. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100272 · Cited by 523
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 520
Private memoirs of a smart meter
Molina-Markham, A., Shenoy, P., Fu, K., Cecchet, E., & Irwin, D. (2010) · Proceedings of the 2nd ACM Workshop on Embedded Sensing Systems for Energy-Efficiency in Building · doi:10.1145/1878431.1878446 · Cited by 511
The PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
Statistical zero knowledge protocols to prove modular polynomial relations
Fujisaki, E., & Okamoto, T. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052225 · Cited by 497
Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090263 · Cited by 493
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Self-citationOptimistic fair exchange of digital signatures
Asokan, N., Shoup, V., & Waidner, M. (2000) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.839935 · Cited by 480
Reasoning about knowledge and probability
Fagin, R., & Halpern, J. Y. (1994) · Journal of the ACM · doi:10.1145/174652.174658 · Cited by 477
Simplified VSS and fast-track multiparty computations with applications to threshold cryptography
Gennaro, R., Rabin, M. O., & Rabin, T. (1998) · Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98 · doi:10.1145/277697.277716 · Cited by 464
Clique is hard to approximate within n/sup 1-ε/
Hastad, J. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548522 · Cited by 458
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1991) · Computational Complexity · doi:10.1007/bf01200056 · Cited by 458
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Short Pairing-Based Non-interactive Zero-Knowledge Arguments
Groth, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_19 · Cited by 440
Privacy-Preserving Solutions for Blockchain: Review and Challenges
Bernal Bernabe, J., Canovas, J. L., Hernandez-Ramos, J. L., Torres Moreno, R., & Skarmeta, A. (2019) · IEEE Access · doi:10.1109/access.2019.2950872 · Cited by 459
“AZero-Knowledge Proof (ZKP) [101] is a cryptographic protocol that allows a party, the prover, to prove to another entity, the verifier, that a given statement is true, without revealing any information except that the proof itself is correct.”
BackgroundBlum, M., De Santis, A., Micali, S., & Persiano, G. (1991) · SIAM Journal on Computing · doi:10.1137/0220068 · Cited by 427
Self-citationRobust Threshold DSS Signatures
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_31 · Cited by 427
Dwork, C., Naor, M., & Sahai, A. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276853 · Cited by 425
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Self-citationOn the Composition of Zero-Knowledge Proof Systems
Goldreich, O., & Krawczyk, H. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539791220688 · Cited by 423
Zero-knowledge from secure multiparty computation
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250794 · Cited by 412
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
Improved Delegation of Computation Using Fully Homomorphic Encryption
Chung, K.-M., Kalai, Y., & Vadhan, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_26 · Cited by 403
Designing programs that check their work
Blum, M., & Kannan, S. (1995) · Journal of the ACM · doi:10.1145/200836.200880 · Cited by 393
Secure k-nearest neighbor query over encrypted data in outsourced environments
Elmehdwi, Y., Samanthula, B. K., & Jiang, W. (2014) · 2014 IEEE 30th International Conference on Data Engineering · doi:10.1109/icde.2014.6816690 · Cited by 386
How to Simulate It – A Tutorial on the Simulation Proof Technique
Lindell, Y. (2017) · Information Security and Cryptography · doi:10.1007/978-3-319-57048-8_6 · Cited by 381
Verifiable Delegation of Computation over Large Datasets
Benabbas, S., Gennaro, R., & Vahlis, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_7 · Cited by 379
Fair Computation of General Functions in Presence of Immoral Majority
Goldwasser, S., & Levin, L. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-38424-3_6 · Cited by 353
Self-citationA model for asynchronous reactive systems and its application to secure message transmission
Pfitzmann, B., & Waidner, M. (2002) · Proceedings 2001 IEEE Symposium on Security and Privacy. S&P 2001 · doi:10.1109/secpri.2001.924298 · Cited by 349
One-way functions are essential for complexity based cryptography
Impagliazzo, R., & Luby, M. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63483 · Cited by 339
Universally Composable Security with Global Setup
Canetti, R., Dodis, Y., Pass, R., & Walfish, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_4 · Cited by 331
Aurora: Transparent Succinct Arguments for R1CS
Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., & Ward, N. P. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-17653-2_4 · Cited by 330
How to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
Bootle, J., Cerulli, A., Chaidos, P., Groth, J., & Petit, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_12 · Cited by 325
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322
Hoepman, J.-H. (2014) · IFIP Advances in Information and Communication Technology · doi:10.1007/978-3-642-55415-5_38 · Cited by 318
Bellare, M., & Palacio, A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45708-9_11 · Cited by 312
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993) · Computational Complexity · doi:10.1007/bf01275486 · Cited by 310
SIA: Secure information aggregation in sensor networks
Chan, H., Perrig, A., Przydatek, B., & Song, D. (2007) · Journal of Computer Security · doi:10.3233/jcs-2007-15104 · Cited by 309
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.180 · Cited by 307
Security and Privacy in Smart Cities: Challenges and Opportunities
Cui, L., Xie, G., Qu, Y., Gao, L., & Yang, Y. (2018) · IEEE Access · doi:10.1109/access.2018.2853985 · Cited by 306
Recursive composition and bootstrapping for SNARKS and proof-carrying data
Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488623 · Cited by 304
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.