Non-interactive zero-knowledge

A non-interactive zero-knowledge (NIZK) proof allows a prover to convince a verifier that a statement $x\in L$ with a single message (no interaction), typically in the common reference string (CRS) model where both parties share a trusted public string sampled by a setup algorithm. Introduced by Blum, Feldman, and Micali — BFM88.

Syntax

A NIZK proof system for language $L$ is a tuple of efficient algorithms $\mathsf{NIZK}=(\mathsf{Setup},\mathsf{Prove},\mathsf{Vrfy})$:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{crs},$ samples a common reference string $\mathsf{crs},$
• $\mathsf{Prove}(\mathsf{crs},x,w)\to \pi ,$ takes a statement $x\in L$ with witness $w$ and outputs a proof $\pi ,$
• $\mathsf{Vrfy}(\mathsf{crs},x,\pi )\to \{0,1\},$ deterministically verifies the proof.

Properties

Completeness

For all $x\in L$ with witness $w$, $\mathsf{Vrfy}(\mathsf{crs},x,\mathsf{Prove}(\mathsf{crs},x,w))=1$ with probability 1 over $\mathsf{crs}\leftarrow \mathsf{Setup}(1^{\lambda })$.

Soundness / Argument

For all $P^{\ast }$, $\mathrm{Pr}\left[\mathsf{Vrfy}(\mathsf{crs},x,\pi )=1\wedge x\notin L\right]\le \mathrm{negl}(\lambda )$ over $\mathsf{crs}\leftarrow \mathsf{Setup}(1^{\lambda })$ and $(x,\pi )\leftarrow P^{\ast }(\mathsf{crs})$.

If soundness holds only against efficient provers (using computational hardness), the system is called a NIZK argument.

Zero-knowledge

There exists an efficient simulator $({\mathcal{S}}_1,{\mathcal{S}}_2)$ where ${\mathcal{S}}_1(1^{\lambda })\to (\mathsf{crs},\mathsf{td})$ outputs a simulated CRS and trapdoor, and ${\mathcal{S}}_2(\mathsf{td},x)\to \pi$ simulates proofs, such that real and simulated $(crs,\pi )$ pairs are computationally indistinguishable.

Variations

NIZK for NP

A NIZK proof system for an $\mathbf{NP}$-complete language, such as circuit satisfiability, and hence, composed with Levin reductions (Karp reductions that also map witnesses in polynomial time), for every language in $\mathbf{NP}$. The restriction matters for constructions that prove statements about their own algorithms: for a language in $\mathbf{P}$, an empty reference string and an empty proof with a verifier that decides the language are complete, sound and zero-knowledge with no assumption — standard.

NIZK arguments for NP

A NIZK argument for an $\mathbf{NP}$-complete language: soundness holds only against efficient provers, which still choose the statement after seeing $\mathsf{crs}$. Every NIZK proof system for NP is one.

Non-adaptively sound NIZK arguments for NP

A NIZK argument for an $\mathbf{NP}$-complete language whose soundness holds only against efficient provers that fix the false statement $x$ before $\mathsf{crs}$ is sampled. Puncturing arguments that hard-wire the false statement $x$ into a hybrid reference string prove this notion directly; the Sahai–Waters argument was shown only non-adaptively sound, and WW24 obtain adaptive soundness for a succinct variant from sub-exponentially secure iO and one-way functions together with polynomial hardness of discrete logarithms or factoring, by complexity leveraging — WW24.

NIZK proofs in the common random string model

A NIZK proof system for NP whose $\mathsf{Setup}$ outputs a uniformly random string and whose soundness holds against unbounded provers that choose the statement after seeing $\mathsf{crs}$ — FLS90.

Simulation-sound NIZK (SS-NIZK)

An SS-NIZK remains sound even against adversaries who have seen simulated proofs. This stronger notion is essential for constructing CCA-secure encryption from NIZK.

zk-SNARK

A Succinct Non-interactive ARgument of Knowledge (zk-SNARK) is a NIZK argument with the additional properties that:

• The proof $\pi$ is short (polylogarithmic in the circuit size)
• Verification is fast (polynomial in $\lambda$ and $|x|$, polylogarithmic in the circuit size) — BCCT13
• The prover has knowledge soundness (a witness can be extracted)

See SNARKs for more detail.

NIZK in the random oracle model

Via the Fiat-Shamir heuristic, any sigma protocol with a superpolynomial-size challenge space can be compiled to a NIZK argument in the random oracle model by replacing the verifier’s random challenge with a hash of the statement and the prover’s commitment — FS86.

Other results

• RSA ⇒ TDP
• Doubly enhanced certified TDP ⇒ NIZK
• OWF + iO ⇒ Non-adaptively sound NIZK argument
• HVZK ⇒ NIZK (Fiat–Shamir) — FS86
• No fixed-construction reduction from Fiat-Shamir to NIZK
• DLIN ⇒ NIZK
• NIZK can be used to convert CPA-secure PKE to CCA-secure PKE — BFM88
• LWE ⇒ NIZK

Participates in

Builds on Non-interactive zero-knowledge

• NIZK proofs with a common random string ⇒ NIZK (via NIZK proofs in the common random string model)
• NIZK argument for NP ⇒ Non-adaptively sound NIZK argument for NP (via NIZK arguments for NP)
• NIZK for NP ⇒ NIZK (via NIZK for NP)
• NIZK proof for NP ⇒ NIZK argument for NP (via NIZK for NP)
• NIZK ⇒ Zaps (Dwork–Naor) (via NIZK proofs in the common random string model)
• CPA-secure PKE + NIZK ⇒ CCA1-secure PKE (Naor–Yung) (via NIZK for NP)
• CPA-secure PKE + NIZK ⇒ CCA2-secure PKE (DDN, Sahai) (via NIZK for NP)

Produces Non-interactive zero-knowledge

• NIZK proofs with a common random string ⇒ NIZK (via NIZK for NP)
• DLIN ⇒ NIZK (via NIZK for NP)
• HVZK ⇒ NIZK (Fiat–Shamir)
• OWF + iO ⇒ Non-adaptively sound NIZK argument (via Non-adaptively sound NIZK arguments for NP)
• Low-noise LPN + DDH ⇒ NIZK argument for NP (via NIZK arguments for NP)
• LWE ⇒ NIZK (via NIZK for NP)
• NIZK argument for NP ⇒ Non-adaptively sound NIZK argument for NP (via Non-adaptively sound NIZK arguments for NP)
• NIZK for NP ⇒ NIZK
• NIZK proof for NP ⇒ NIZK argument for NP (via NIZK arguments for NP)
• QR ⇒ NIZK proofs with a common random string (Blum–De Santis–Micali–Persiano) (via NIZK proofs in the common random string model)
• SNARK + OWF ⇒ NIZK argument (via Non-adaptively sound NIZK arguments for NP)
• Sub-exponential DDH ⇒ NIZK argument for NP (via NIZK arguments for NP)
• SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
• Doubly enhanced certified TDP ⇒ NIZK (via NIZK proofs in the common random string model)

Barriers

• No fixed-construction reduction from Fiat-Shamir to NIZK