Non-interactive zero-knowledge proof

Verification succeeds for all ${\displaystyle \sigma \in \operatorname {Setup} \left(1^{k}\right)}$ and every ${\displaystyle (y,w)\in R_{\sigma }}$.

More formally, for all k, all ${\displaystyle \sigma \in \operatorname {Setup} \left(1^{k}\right)}$, and all ${\displaystyle (y,w)\in R_{\sigma }}$:

${\displaystyle \Pr \left[\pi \gets \operatorname {Prove} (\sigma ,y,w):\operatorname {Verify} (\sigma ,y,\pi )=\mathrm {accept} \right]=1}$

Soundness requires that no prover can make the verifier accept a wrong statement ${\displaystyle y\not \in L}$ except with some small probability. The upper bound of this probability is referred to as the soundness error of a proof system.

More formally, for every malicious prover, ${\displaystyle {\tilde {P}}}$, there exists a negligible function, ${\displaystyle \nu }$, such that

${\displaystyle \Pr \left[\sigma \gets \operatorname {Setup} \left(1^{k}\right),(y,\pi )\gets {\tilde {P}}(\sigma ):y\not \in L\land \operatorname {Verify} (\sigma ,y,\pi )=\mathrm {accept} \right]=\nu (k)\;.}$

The above definition requires the soundness error to be negligible in the security parameter, k. By increasing k the soundness error can be made arbitrary small. If the soundness error is 0 for all k, we speak of perfect soundness.

A non-interactive proof system ${\displaystyle (\operatorname {Setup} ,\operatorname {Prove} ,\operatorname {Verify} )}$ is multi-theorem zero-knowledge, if there exists a simulator, ${\displaystyle \operatorname {Sim} =(\operatorname {Sim} _{1},\operatorname {Sim} _{2})}$, such that for all non-uniform polynomial time adversaries, ${\displaystyle {\mathcal {A}}}$,

${\displaystyle \Pr \left[\sigma \gets \operatorname {Setup} (1^{k}):{\mathcal {A}}^{{\operatorname {Prove} }(\sigma ,.,.)}(\sigma )=1\right]\equiv \Pr \left[(\sigma ,\tau )\gets \operatorname {Sim} _{1}:{\mathcal {A}}^{{\operatorname {Sim} }(\sigma ,\tau ,.,.)}(\sigma )=1\right]}$

Here ${\displaystyle \operatorname {Sim} (\sigma ,\tau ,y,w)}$ outputs ${\displaystyle \operatorname {Sim} _{2}(\sigma ,\tau ,y)}$ for ${\displaystyle (y,w)\in R_{\sigma }}$ and both oracles output failure otherwise.