Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Abstract
In this paper the generality and wide applicability of Zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff is demonstrated. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages in NP fl CONP. Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula, in particular, without yielding neither a
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
(1979) · Cited by 43,841
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
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
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
Cited by
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
Practical graph isomorphism, II
McKay, B. D., & Piperno, A. (2014) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2013.09.003 · Cited by 1,597
Security and Composition of Multiparty Cryptographic Protocols
Canetti, R. (2000) · Journal of Cryptology · doi:10.1007/s001459910006 · Cited by 1,403
Designated Verifier Proofs and Their Applications
Jakobsson, M., Sako, K., & Impagliazzo, R. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_13 · Cited by 817
Dolev, D., Dwork, C., & Naor, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795291562 · Cited by 746
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-citationCharm: a framework for rapidly prototyping cryptosystems
Akinyele, J. A., Garman, C., Miers, I., Pagano, M. W., Rushanan, M., Green, M., & Rubin, A. D. (2013) · Journal of Cryptographic Engineering · doi:10.1007/s13389-013-0057-3 · Cited by 675
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
Universally Composable Commitments
Canetti, R., & Fischlin, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_2 · Cited by 621
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
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
Self-citationDelegating 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
Optimistic 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
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
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
Self-citationDamgård, I., Fitzi, M., Kiltz, E., Nielsen, J. B., & Toft, T. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_15 · Cited by 443
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
Self-citationTowards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
De Feo, L., Jao, D., & Plût, J. (2014) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2012-0015 · Cited by 405
Designing programs that check their work
Blum, M., & Kannan, S. (1995) · Journal of the ACM · doi:10.1145/200836.200880 · Cited by 393
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
Property-based attestation for computing platforms: caring about properties, not mechanisms
Sadeghi, A.-R., & Stüble, C. (2005) · Proceedings of the 2004 workshop on New security paradigms - NSPW '04 · doi:10.1145/1065907.1066038 · Cited by 371
Lagendijk, R. L., & Barni, M. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2219653 · Cited by 336
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
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
A personal view of average-case complexity
Impagliazzo, R. (2002) · Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference · doi:10.1109/sct.1995.514853 · Cited by 298
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
Robust 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
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
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
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 270
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
Self-citationModern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Self-citationDwork, C., & Naor, M. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892117 · Cited by 264
Quantum cryptography beyond quantum key distribution
Broadbent, A., & Schaffner, C. (2016) · Designs, Codes and Cryptography · doi:10.1007/s10623-015-0157-4 · Cited by 230
“This technique therefore provides an alternative to the classical rewinding paradigm, and is used to show that the Goldreich-Micali-Wigderson graph 3-coloring protocol [122] is zero-knowledge against quantum attacks.”
Universal Designated-Verifier Signatures
Steinfeld, R., Bull, L., Wang, H., & Pieprzyk, J. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-40061-5_33 · Cited by 226
“Implementing the above scheme using a generic zero-knowledge NP proof system [18] would yield a very inefficient and randomized designation and inefficient DV verification.”
MethodPrivacy-preserving cloud computing on sensitive data: A survey of methods, products and challenges
Domingo-Ferrer, J., Farràs, O., Ribes-González, J., & Sánchez, D. (2019) · Computer Communications · doi:10.1016/j.comcom.2019.04.011 · Cited by 202
Jha, S., Kruger, L., & McDaniel, P. (2005) · Lecture Notes in Computer Science · doi:10.1007/11555827_23 · Cited by 192
“We compared our protocols for WAP with a simple strategy of ap proximating the function x+y n+m by a circuitC and then using standard constructions [21, 22, 52].”
MethodRobust and Efficient Sharing of RSA Functions
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_13 · Cited by 189
A blockchain-based scheme for privacy-preserving and secure sharing of medical data
Huang, H., Zhu, P., Xiao, F., Sun, X., & Huang, Q. (2020) · Computers & Security · doi:10.1016/j.cose.2020.102010 · Cited by 185
“Furthermore, zero-knowledge proof ( Goldreich et al., 1991 ) ill be employed to address the second issue, whose funcion is that the prover can convince the verifier that the asertion is correct (the needs are met) without providing the erifier with any useful information (any private data).”
BackgroundShort Linkable Ring Signatures for E-Voting, E-Cash and Attestation
Tsang, P. P., & Wei, V. K. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-31979-5_5 · Cited by 183
Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition
Pass, R. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-39200-9_10 · Cited by 181
A complete problem for statistical zero knowledge
Sahai, A., & Vadhan, S. (2003) · Journal of the ACM · doi:10.1145/636865.636868 · Cited by 178
“An Example for GRAPH ISOMORPHISM For illustrative purposes, here we explicitly describe what happens when the reduction to and proof system for STATISTICAL DIFFERENCE are applied to the wellknown public-coin perfect zero-knowledge proof system for GRAPH ISOMORPHISM [Goldreich et al. 1991]: Perfect zero-knowledge proo…”
BackgroundMethodInfluentialOn the existence of 3-round zero-knowledge protocols
Hada, S., & Tanaka, T. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055744 · Cited by 175
Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model
Unruh, D. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_25 · Cited by 160
“A full version is provided in [15].]”
The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives
Nguyen, M.-H. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_25 · Cited by 7
“3 This equivalence would be non-black-box as the known construction of OT from honest OT is non-black-box since it uses the zero-knowledge proofs of [ 12 ] ( see [9]).”
MethodFairProof : Confidential and Certifiable Fairness for Neural Networks
Yadav, C., Chowdhury, A. R., Boneh, D., & Chaudhuri, K. (2024) · arXiv · doi:10.48550/arxiv.2402.12572 · Cited by 2
“To do this, we rely on Succinct Zero Knowledge Proofs Goldwasser et al. (1985); Goldreich et al. (1991).”
BackgroundMethod
Metadata
- Authors
- Goldreich, O., Micali, S., & Wigderson, A.
- Venue
- Journal of the ACM
- Published
- 1991-07
- Volume
- 38
- Issue
- 3
- Pages
- 690-728
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2011112377
- Cited by
- 1,349
- References
- 53
- FWCI
- 10.46
- Type
- journal article
- Language
- en
- Open access
- closed
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.