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},\text{Prove},\mathsf{Vrfy})$:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{crs},$ samples a common reference string $\mathsf{crs},$
• $\text{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,\text{Prove}(\mathsf{crs},x,w))=1$ with probability 1 over $\mathsf{crs}\leftarrow \mathsf{Setup}(1^{\lambda })$.

Soundness / Argument

For all efficient $P^{\ast }$: $\mathrm{Pr}[\mathsf{Vrfy}(\mathsf{crs},x,P^{\ast }(\mathsf{crs},x))=1\wedge x\notin L]\le \mathrm{negl}(\lambda ).$

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 (polylogarithmic in the statement size)
• 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 can be compiled to a NIZK argument in the random oracle model by replacing the verifier’s random challenge with a hash of the prover’s commitment.

Other results

• NIZK for all NP from trapdoor permutations (hence from RSA or DL) in the CRS model — BFM88
• NIZK from iO and OWF in the plain model (no CRS) — SW14
• Fiat-Shamir compiles sigma protocols to NIZK in the ROM — FS86; but is insecure for general interactive proofs — GK03
• NIZK → COM: every NIZK scheme gives a non-interactive commitment
• Pairing-based NIZK (Groth-Sahai proofs, Groth16) achieves constant or logarithmic proof size — Gro16
• NIZK can be used to convert CPA-secure PKE to CCA-secure PKE — BFM88
• NIZK from LWE via hash-and-sign signatures and SIS-based commitments — standard