Non-interactive zero-knowledge and its applications
Open accessAbstract
We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
Noninteractive proof systems, first introduced by Blum et al., do not require the concurrent availability of both parties.
“Conversely, the noninteractive proof systems, first introduced by Blum et al. [137], do not require the concurrent availability of both parties.”
From A Survey of Self-Sovereign Identity Ecosystem (2021) · cites this paper as [137]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713 · see citing works
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 · see citing works
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 · see citing works
Self-citationA Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S. M., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,803 · see citing works
Self-citationHow to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. M. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,309 · see citing works
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 · see citing works
Self-citationZero-knowledge proofs of identity
Feige, U., Fiat, A., & Adi Shamir, Z. (1988) · Journal of Cryptology · doi:10.1007/bf02351717 · Cited by 1,033 · see citing works
Theory and application of trapdoor functions
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.95 · Cited by 1,011 · see citing works
New Directions in Cryptography
Diffie, W., & Hellman, M. E. (2022) · ACM eBooks · doi:10.1145/3549993.3550007 · Cited by 672 · see citing works
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
Goldreich, O., Micali, S. M., & Wigderson, A. (1986) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1986.47 · Cited by 549 · see citing works
Self-citationZero knowledge proofs of identity
Fiege, U., Fiat, A., & Shamir, A. (1987) · doi:10.1145/28395.28419 · Cited by 403 · see citing works
Private coins versus public coins in interactive proof systems
Goldwasser, S., & Sipser, M. (1986) · doi:10.1145/12130.12137 · Cited by 401 · see citing works
Blum, M. (1981) · International Cryptology Conference · Cited by 242 · see citing works
Self-citationThe complexity of perfect zero-knowledge
Fortnow, L. (1987) · doi:10.1145/28395.28418 · Cited by 170 · see citing works
Why and how to establish a private code on a public network
Goldwasser, S., Micali, S. M., & Tong, P. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.100 · Cited by 79 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 4
- M. Blum, L. Blum and M. Shub,A simple and secure pseudo-randomnumber generator,SIAM Journal of Computing, 1986
- M. Blum and S. Micali, How To Generate Se- quences Of Cryptographically Strong Pseudo-Random Bits, SIAM J. on Computing, Vol. 13, Nov 1984, pp. 850-864
- Diffie, W., and M.E. Hellman, New Direc- tions in Cryptography,IEEE Trans. on Inform. The- ory,
- S. Goldwasser, and S. Micah, Probabilistic Encrypiion, JCSS Vol. 28, No. 2, April 1984.
Cited by
Sorted by citations
Bitcoin and beyond: a technical survey on decentralized digital currencies
Tschorsch, F., & Scheuermann, B. (2016) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2016.2535718 · Cited by 1,690 · see citing works
On 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 · see citing works
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424 · see citing works
Self-citationA Survey of Self-Sovereign Identity Ecosystem
Soltani, R., Nguyen, U. T., & An, A. (2021) · Security and Communication Networks · doi:10.1155/2021/8873429 · Cited by 131 · see citing works
Lenstra, A. K., Kleinjung, T., & Thomé, E. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42001-6_9 · Cited by 13 · see citing works
- Authors
- Blum, M., Feldman, P., & Micali, S.
- Affiliations
- University of California, Berkeley (US)
- Massachusetts Institute of Technology (US)
- ORCID
- Blum, Manuel
- Venue
- Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88
- Publisher
- ACM Press
- Published
- 1988
- Pages
- 103-112
- OpenAlex
- W2079913403
- Cited by
- 904
- References
- 15
- Citations by year
- 2026: 21 · 2025: 60 · 2024: 54 · 2023: 54 · 2022: 52 · 2021: 58 · 2020: 53 · 2019: 50 · 2018: 34 · 2017: 32 · 2016: 32 · 2015: 39 · 2014: 29 · 2013: 29 · 2012: 24
- FWCI
- 4.91
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Authentication Protocols Security
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- non-interactive zero-knowledge proofs, zero-knowledge proofs, public-key cryptosystems, chosen ciphertext attack, public-key encryption
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
