The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Noninteractive Zero-Knowledge
Abstract
This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge 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
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-citationThe 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
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-citationGoldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Self-citationHow to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Self-citationHow to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
Self-citationA Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036
Self-citationTheory 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
Probabilistic algorithm for testing primality
Rabin, M. O. (1980) · Journal of Number Theory · doi:10.1016/0022-314x(80)90084-0 · Cited by 863
Cited by
Random 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
Conjunctive, Subset, and Range Queries on Encrypted Data
Boneh, D., & Waters, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_29 · Cited by 1,432
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
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
Pinocchio: 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
Dolev, D., Dwork, C., & Naor, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795291562 · Cited by 746
Bellare, M., Micciancio, D., & Warinschi, B. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-39200-9_38 · Cited by 732
Quadratic Span Programs and Succinct NIZKs without PCPs
Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_37 · 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-citationLossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Self-citationNon-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
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-citationCoercion-resistant electronic elections
Juels, A., Catalano, D., & Jakobsson, M. (2005) · Proceedings of the 2005 ACM workshop on Privacy in the electronic society · doi:10.1145/1102199.1102213 · Cited by 414
Public-Key Cryptosystems Resilient to Key Leakage
Naor, M., & Segev, G. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_2 · Cited by 403
Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures
Groth, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11935230_29 · Cited by 390
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
Towards realizing random oracles: Hash functions that hide all partial information
Canetti, R. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052255 · Cited by 365
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
Micali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
Self-citationRobust 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
Self-citationNon-interactive cryptocomputing for NC/sup 1/
Sander, T., Young, A., & Yung, M. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814630 · Cited by 279
Randomizable Proofs and Delegatable Anonymous Credentials
Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., & Shacham, H. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_7 · Cited by 269
Dwork, C., & Naor, M. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892117 · Cited by 264
Securing threshold cryptosystems against chosen ciphertext attack
Shoup, V., & Gennaro, R. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054113 · Cited by 257
Parno (2016) · doi:10.1145/2856449 · Cited by 212
Metadata
- Authors
- Blum, M., De Santis, A., Micali, S., & Persiano, G.
- Venue
- SIAM Journal on Computing
- Published
- 1991-12
- Volume
- 20
- Issue
- 6
- Pages
- 1084-1118
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W259957856
- Cited by
- 427
- References
- 17
- FWCI
- 7.53
- 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.