7
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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$
    – Marc Ilunga
    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$
    – Marc Ilunga
    Jan 6 at 23:51

0

Reset to default

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.