Knowledge Proofs

You know something, if when given an input that includes Knowledge, you can efficiently extract the knowledge from that input.

Defintion

A Protocol $(P,V)$ is a Proof of knowledge for an Effective Relation $R$ if it is:

1. Complete ($\forall (x,w)\in R$, if $P$ runs on input $(x,w)$ and $V$ on input $x$, then $V$ outputs accept)
2. Mathematically Sound (There exists PPT $ϵ$ s.t $\forall x\in X,\hat{P}$ with a non-negligable probability of making $V$ accept, $ϵ$ can interact with Rewindable $\hat{P}$ to produce with overwhelming probability, $w\in W$ s.t $(x,w)\in R$)

Intuition

• With a Protocol that defines $(\hat{P},V)$. For all possibly cheating Protocols $\hat{P}$ that make $V$ output accept, we can efficiently extract a Witness from $\hat{P}$ by Rewinding it.