Non-Interactive Zero-Knowledge

Definition

Let $R$ be a relation, corresponding to an NP language $L$. A Non-Interactive Zero-Knowledge (NIZK) proof system for $R$ is a tuple of polynomial-time algorithms $\Pi = (I, P, V)$ specified as follows:

  • The randomized algorithm $I$ takes as input the security parameter and outputs a common reference string $\omega$
  • The randomized algorithm $P$, given $\omega$ and $x \in R$ and a witness $\zeta$ outputs a proof $\pi$
  • The deterministic algorithm $V$, given $\omega$, an instance $x$ and a proof $\pi$ outputs either 0 (reject) or 1 (accept)

Properties

A NIZK proof of system satisfies:

  • completeness if $\forall x \in L$:
\[Pr[V(\omega, x, \pi) = 1 : \omega \samples I(1^\lambda), \pi \samples P(\omega, x, \zeta)]\]
  • soundness if $\forall x \not\in L$ and $\forall P^*$ (even computationally unbounded):
\[Pr[V(\omega, x, \pi) = 1 : \omega \samples I(1^\lambda), \pi \samples P^*(\omega, x)] \in negl(\lambda)\]
  • zero-knowledge if $\exists$ PPT simulator $S = (S_0, S_1)$, s.t. $\forall x \in L$,
\[\{ \omega, S_1(\tau, x) : (\omega, \tau) \samples S_0(1^\lambda) \} \approx_c \{ \omega, P(\omega, x, \zeta): \omega \samples I(1^\lambda) \}\]