Zero Knowledge

Consider other knowledge assumptions like

Notation

\(P\) Prover
\(P^{*}\) Malicious Prover
\(V\) Verifier
\(V^{*}\) Malicious Verifier
\(L \subseteq \Sigma^{*}\) Language, where \(\Sigma\) is the set of all words of the language Generally, \(L = \{x| \exists\pi, V(x,\pi) = ACCEPT \}\)
\(x\in L\) is an instance of the language

Correct \(P\) and correct \(V\) should always succeed.
\(\forall (x,w) \in \mathcal{R}_{\mathcal{L}}: Pr[V(x,\pi)=1| \pi \leftarrow P(x,w)]=1\)

An honest \(V\) always rejects \(x \not\in \mathcal{L}\) for any prover \(P^*\).
Soundness protects a verifier from accepting false proofs from malicious provers.
\(Pr[V(x,\pi^{*})=1|\pi^{*}\leftarrow P^{*}(x)]\le \epsilon(x,\lambda)\)

This requires the existence of a PPT extractor \(\mathcal{E}\), that given two accepting transcripts \(\mathcal{T}_{1}\) and \(\mathcal{T}_{2}\) for a statement such that \(\mathcal{T}_{1} \ne \mathcal{T}_{2}\), outputs a witness \(wit\) such that \((statement, wit)\in \mathcal{L}\).
\(\exists\) PPT extractor \(\mathcal{E}\) such that \(\forall x\) and \(\forall\) PPT \(P^{*}\):
- \(Pr[(x, \mathcal{E}^{P^{*}}(x))\in \mathcal{R}_{\mathcal{L}}] + \epsilon(x,\lambda) \ge Pr[V(x,\pi^{*})=1| \pi^{*}\leftarrow P^{*}(x)]\)
The knowledge soundness protects the verifier.

As opposed to knowledge soundness, zero knowledge protects the prover against malicious verifiers.