Proof of knowledge

An interactive proof of knowledege for relation $R$ with knowledge error $\kappa$ is a two party protocol with a prover $P$ and a verifier $V$ with the following two properties:

1. Completeness: if $(x,w)\in R$, the prover P who knows witness $w$ for $x$ succeeds in convincing the verifier $V$ of his knowledge. More formally: $Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1$
2. Validity: Validity requires that the success probability of a knowledge extractor $E$ in extracting the witness, given oracle access to a possibly malicious prover ${\tilde {P}}$, must be at least as high as the success probability of the prover ${\tilde {P}}$ in convincing the verifier. This Property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier.

Details on the definition

This is the rigorous definition of Validity:

There exists a polynomial-time machine $E$, given oracle access to ${\tilde {P}}$, such that for every ${\tilde {P}}$ and every $x\in \;dom\;R$, it is the case that $E^{{\tilde {P}}(x)}(x)\in R(x)\cup \{\bot \}$ and $Pr(E^{{\tilde {P}}(x)}(x)\in R(x))\geq Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).$

$R(x)$ is the set of all witnesses for public value $x$, while the result $\bot$ signifies that the Turing machine $E$ did not come to a conclusion.

The knowledge error $\kappa (x)$ denotes the probability that the verifier $V$ might accept $x$, even though the prover does in fact not know a witness $w$. The knowledge extractor $E$ is used to express what is meant by the knowledge of a Turing machine. If $E$ can extract $w$ from ${\tilde {P}}$, we say that ${\tilde {P}}$ knows the value of $w$.

See also

• Cryptographic protocol
• Zero-knowledge proof
• interactive proof system
• Topics in cryptography
• Zero-knowledge password proof

External links

• On Defining Proofs of Knowledge