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} $$

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 6 at 23:46
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 6 at 23:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.