Proof of knowledge

In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds 'convincing' a verifier that it knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. We are mostly interested in what can be proven by polynomical time machines. As the program of the prover, does not necessarily spit out the knowledge itself, as is the case for zero-knowledge proofs, a machine with a different program, called the knowledge extractor is introduced to capture this idea.

A 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