Non-interactive zero-knowledge and its applications

By Manuel Blum, Paul Feldman, Silvio Micali. 1988

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Dan Boneh
2. Eli Ben-Sasson
3. Srinath T. V. Setty
4. Brent Waters
5. Craig Gentry
6. Jens Groth
7. Shai Halevi
8. Mihir Bellare

Citations in the corpus

• Chosen-Ciphertext Security from Identity-Based Encryption (2004, methodology): “This technique uses as building blocks any CPA-secure public-key encryption scheme and any non-interactive zero-knowledge (NIZK) proof system for all of NP [6, 31].”
• Handbook of Applied Cryptography (2018, background): “[163].”
• Modern Cryptography: Theory and Practice (2003, methodology): “Blum, Feldman and Micali propose a method for achieving non-interactive ZK (NIZK) if P and V share random challenge bits [44].”
• Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008, methodology): “To address these issues, the common random string (CRS) model was introduced [7, 6].”
• Verifiable random functions (1999, methodology): “Suchinteraction could be removed by using noninter-active zero-knowledge proofs (NIZK) [BFM88, BDMP91], as done by Bellare and Goldwasser [BG89].”
• How to Break the Direct RSA-Implementation of Mixes (1990, background): “[2], but we have heard doubts about it; an interactive system, on the other hand, is quite unwieldy if several MIXes in a row are used [4]).”
• Security and Privacy on Blockchain (2019, background): “Asavariant of zero-knowledge proofs, it is shown in [18] that, with the non-interactive variant of zero-knowledge proofs, coined as NIZK, one can achieve computational zero-knowledge without requiring certifier and verifier to interact at all, provided that the certifier and the verifier shares a…”
• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “Thus, it is desirable for the proof to be non-interactive [25, 55, 23]: the server just send the claimed output z̃, along with a non-interactive proof string π that attests that z̃ is the correct output.”
• Universally composable security: a new paradigm for cryptographic protocols (2001, methodology): “Nonetheless, we show that in settings where parties have access to a set of servers, at most a minority of which may be corrupted, standard cryptographic techniques (e.g., [ BGW 88, RB 89, CFGN 96]) can be used to carry out practically any cryptographic task in a universally composable way.”
• Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes (2013, methodology): “By using non-interactive zero knowledge (NIZK, [3]), the prover can create a proof π, s.”