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 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

• RSA ⇒ TDP
• TDP ⇒ NIZK
• DLOG ⇒ TDP
• Hash function + iO ⇒ NIZK
• ZKP ⇒ NIZK
• No reduction from Fiat-Shamir to NIZK
• NIZK ⇒ COM
• BDH ⇒ NIZK
• NIZK can be used to convert CPA-secure PKE to CCA-secure PKE — BFM88
• LWE ⇒ Lattice-based signatures

Participates in

Builds on Non-interactive zero-knowledge

• Arithmetization + NIZK + PCS ⇒ SNARK
• NIZK ⇒ COM

Produces Non-interactive zero-knowledge

• BDH ⇒ NIZK
• Fiat-Shamir + Honest-verifier ZK (HVZK) ⇒ NIZK
• Hash function + iO ⇒ NIZK
• interactive protocol + ROM ⇒ NIZK
• PCS ⇒ NIZK
• ROM + ZKP ⇒ NIZK
• SNARK ⇒ NIZK
• SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
• TDP ⇒ NIZK
• ZKP ⇒ NIZK

Barriers

• No reduction from Fiat-Shamir to NIZK