Proof of Knowledge of secret s
Informally, protocol (P,V) on public input x,
is a Proof of knowledge of s if:
a polynomial time extraction algorithm E s.t EP(x) computes s in expected 1/prob(V accepts x ) calls to P
whenever (x,s) e R and P has private input s, V accepts x.
EP(x): E has black box access to P repeatedly on the same random tape.
Let R be an NP relation. Let (x,s) e R.