# Proof of Knowledge & Rewinding Lemma

I'm somewhat confused about how the definition of a proof of knowledge relates to the Theorem 19.1 in Boneh-Shoup (http://toc.cryptobook.us/book.pdf), particularly in relation to Schnorr's protocol for proof of knowledge of a discrete logarithm.

As far as I'm aware, the standard definition of a "proof of knowledge" is the existence of an efficient knowledge extractor $$\mathcal{E}$$ that has access to a (possibly malicious) prover $$P^*$$ such that: $$\forall y\in\mathcal{Y}\ \forall P^*\ \Pr[(x,y)\in\mathcal{R}:x\leftarrow\mathcal{E}^{P^*}(y)]\ge\Pr[(P^*(y)\leftrightarrow V(y))\rightarrow\mathrm{accept}]-\kappa$$ Where $$\kappa$$ is therefore the probability that a (possibly malicious) prover $$P^*$$ convinces the verifier $$V$$ without knowing the witness $$x$$.

Theorem 19.1 in Boneh-Shoup (which uses the rewinding lemma) states that if an adversary $$\mathcal{A}$$ (playing the role of a potentially malicious prover $$P^*$$), who does not know the witness, can make the verifier $$V$$ accept with advantage $$\epsilon$$, then there exists an adversary $$\mathcal{B}$$ who can "rewind" $$\mathcal{A}$$ to extract the witness $$x$$ with advantage $$\epsilon'\ge\epsilon^2-\frac{\epsilon}{|\mathcal{C}|}$$, where $$\mathcal{C}$$ is the challenge set.

My main question is how does the equation defining a POK relate to the equation in Theorem 19.1?

• Since adversary $$\mathcal{B}$$ is essentially working as a knowledge extractor, can we formulate $$\mathcal{B}$$'s advantage $$\epsilon$$' as being $$\epsilon'=\Pr[(x,y)\in\mathcal{R}:x\leftarrow\mathcal{E}^{P^*}(y)]$$?
• Since adversary $$\mathcal{A}$$ is acting as a (potentially malicious) prover, can we formulate $$\mathcal{A}$$'s advantage $$\epsilon$$ as being$$\epsilon=\Pr[(P^*(y)\leftrightarrow V(y))\rightarrow\mathrm{accept}]$$?

If we can, then there must be some kind of relationship between the knowledge error $$\kappa$$ and $$\mathcal{A}$$'s advantage $$\epsilon$$? Potentially: \begin{aligned} \Pr[(P^*(y)\leftrightarrow V(y))\rightarrow\mathrm{accept}]-\kappa&=\epsilon^2-\frac{\epsilon}{|\mathcal{C}|}\\ \epsilon-\kappa&=\epsilon^2-\frac{\epsilon}{|\mathcal{C}|} \end{aligned}

• That theorem establishes the security of Schnorr's identification protocol with a reduction to the discrete log. Though, the POK is a component of the ID scheme and had interesting properties is nice; in the end we are analysing the security of an ID protocol (that happens to be based on a POK). The rewinding lemma has been the main tool for proving security. An issue with this is the looseness of the bound. There are a number of newer work trying to break this "square root" barrier. Commented Jan 6, 2023 at 23:46
• Additionally, the reduction to the DLOG in the theorem can be seen as taking advantage of not only the special soundness of the POK which guarantees extraction is possible with 2 appropriate accepting transcript so indeed the reduction to DLOG works. Commented Jan 6, 2023 at 23:51