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

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
• TDP ⇒ NIZK
• OWF + iO ⇒ NIZK
• 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

Produces Non-interactive zero-knowledge

• DLIN ⇒ NIZK
• HVZK ⇒ NIZK (Fiat–Shamir)
• OWF + iO ⇒ NIZK
• LWE ⇒ NIZK
• SNARK + OWF ⇒ NIZK
• SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
• TDP ⇒ NIZK

Barriers

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