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$:
- soundness if $\forall x \not\in L$ and $\forall P^*$ (even computationally unbounded):
- zero-knowledge if $\exists$ PPT simulator $S = (S_0, S_1)$, s.t. $\forall x \in L$,