The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Zero-knowledge from secure multiparty computation
Abstract
We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.
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
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756 · cited 1×
“Here the O(log n) multiplicative overhead results from the use of Shamir’s secret sharing [54] (more precisely, the variant of this secret-sharing due to Franklin and Yung [15]), which requires the field size to be larger than the number of players.”
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
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
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
Goldreich, O. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511721656 · Cited by 1,805
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
Foundations of Cryptography: Volume 2, Basic Applications
Goldreich, O. (2004) · Cited by 1,592
Multiparty unconditionally secure protocols
Chaum, D., Crépeau, C., & Damgard, I. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62214 · Cited by 1,544
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
Security and Composition of Multiparty Cryptographic Protocols
Canetti, R. (2000) · Journal of Cryptology · doi:10.1007/s001459910006 · Cited by 1,403
Foundations of Cryptography: Basic Tools
Goldreich, O. (2000) · Cambridge University Press eBooks · Cited by 1,019
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
Verifiable secret sharing and multiparty protocols with honest majority
Rabin, T., & Ben-Or, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73014 · Cited by 930
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
Smolensky, R. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.28404 · Cited by 845
Bit commitment using pseudorandomness
Naor, M. (1991) · Journal of Cryptology · doi:10.1007/bf00196774 · Cited by 807
Definitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
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
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73012 · Cited by 575
Small-Bias Probability Spaces: Efficient Constructions and Applications
Naor, J., & Naor, M. (1993) · SIAM Journal on Computing · doi:10.1137/0222053 · Cited by 560
Coin flipping by telephone a protocol for solving impossible problems
Blum, M. (1983) · ACM SIGACT News · doi:10.1145/1008908.1008911 · Cited by 518
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
Founding Cryptography on Oblivious Transfer – Efficiently
Ishai, Y., Prabhakaran, M., & Sahai, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-85174-5_32 · Cited by 460
Self-citationMicali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Perfect Non-interactive Zero Knowledge for NP
Groth, J., Ostrovsky, R., & Sahai, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_21 · Cited by 381
Self-citationNotions of Reducibility between Cryptographic Primitives
Reingold, O., Trevisan, L., & Vadhan, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24638-1_1 · Cited by 298
Communication complexity of secure computation (extended abstract)
Franklin, M., & Yung, M. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129780 · Cited by 268
Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator
Damgård, I., & Ishai, Y. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_23 · Cited by 175
Self-citationLinear zero-knowledge---a note on efficient zero-knowledge proofs and arguments
Cramer, R., & Damgård, I. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258635 · Cited by 170
Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields
Chen, H., & Cramer, R. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_31 · Cited by 168
Communication preserving protocols for secure function evaluation
Naor, M., & Nissim, K. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380855 · Cited by 165
Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free?
Cramer, R., & Damgård, I. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055745 · Cited by 159
Scalable Secure Multiparty Computation
Damgård, I., & Ishai, Y. (2006) · Lecture notes in computer science · doi:10.1007/11818175_30 · Cited by 143
Self-citationSecure multi-party computation made simple
Maurer, U. M. (2005) · Discrete Applied Mathematics · doi:10.1016/j.dam.2005.03.020 · Cited by 112
OT-Combiners via Secure Computation
Harnik, D., Ishai, Y., Kushilevitz, E., & Nielsen, J. B. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78524-8_22 · Cited by 96
Self-citationOn the complexity of interactive proofs with bounded communication
Goldreich, O., & Håstad, J. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00116-1 · Cited by 91
An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions
Kilian, J., & Petrank, E. (1998) · Journal of Cryptology · doi:10.1007/s001459900032 · Cited by 90
Black-box constructions for secure computation
Ishai, Y., Kushilevitz, E., Lindell, Y., & Petrank, E. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132531 · Cited by 79
Self-citationSemi-honest to Malicious Oblivious Transfer—The Black-Box Way
Haitner, I. (2008) · Springer eBooks · doi:10.1007/978-3-540-78524-8_23 · Cited by 73
Kalai, Y. T., & Raz, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70583-3_44 · Cited by 67
Reducibility and Completeness in Private Computations
Kilian, J., Kushilevitz, E., Micali, S. M., & Ostrovsky, R. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539797321742 · Cited by 61
Self-citationReducibility and completeness in multi-party private computations
Kushilevitz, E., Micali, S. M., & Ostrovsky, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365743 · Cited by 50
Self-citationSuccinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP
Kalai, Y. T., & Raz, R. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.74 · Cited by 28
Boyar, J., Gilles Brassard, A., & Peralta, R. (1995) · Journal of the ACM · doi:10.1145/227683.227686 · Cited by 13
Cited by
Multiparty Computation from Somewhat Homomorphic Encryption
Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_38 · Cited by 1,331
Secure Multiparty Computation and Secret Sharing
Cramer, R., Damgård, I. B., & Nielsen, J. B. (2015) · doi:10.1017/cbo9781107337756 · Cited by 595
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
Founding Cryptography on Oblivious Transfer – Efficiently
Ishai, Y., Prabhakaran, M., & Sahai, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-85174-5_32 · Cited by 460
Self-citationStatus report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413 · Cited by 395
Metadata
- Authors
- Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A.
- Venue
- Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2007-06-11
- Pages
- 21-30
- OpenAlex
- W1980227445
- Cited by
- 412
- References
- 44
- FWCI
- 5.64
- Type
- conference paper
- 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.