I have studied the Schnorr identification scheme, and I came across the security proof.

My question is regarding the following: $$\begin{align} \text{Pr}\left[\text{DLog}_{\mathcal{A}',\mathcal{G}}\left(n\right)=1\right] &= \text{Pr}_{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right)\wedge r_1\neq r_2 \right] \\ &\geq \text{Pr}_{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right) \right]- \text{Pr}_{\omega,r_1,r_2}\left[r_1=r_2\right] \\ &= \sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \left(\delta_\omega\right)^2}- 1/q \\ &\geq \left(\sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \delta_\omega}\right )^2 -1/q \\ &= \delta\left(n\right)^2-1/q \end{align}$$

With $\delta_\omega \stackrel{def}{=} \text{Pr}_r\left[V\left(\omega,r\right)=1\right]$ being the probability that the adversary will succeed in the identification experiment given that we use $\omega$ (random choices) and $r$ (the challenge).

When we move from the 2nd row to the 3rd, we assume that the event that the adversary correctly responds to the challenge $r_1$ is independent of the event that the adversary correctly responds to the challenge $r_2$.

But, we have no knowledge on how $\mathcal{A}$ is acting - so how can we assume these events are independent?


1 Answer 1


I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728.

An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (we can think of B as whoever wants to break the scheme, and presupposes the existence of A):

  1. first, B plays the role of the verifier, and expect A (playing the prover role) send w;
  2. B send r1, and wait for the A's answer;
  3. B rewinds A, so that A’s internal state is exactly the same as it was at the end of step 1;
  4. B sends a random and independent r2; waits for the A answer.

So B may be ignorant about how A works, but s/he is who sets A independent challenges/answers, and takes advantage of it.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.