I was introduced to the QR-protocol that shows that a number y is a quadratic residue modulo x through an interactive protocol. The protocol is perfect zero-knowledge but it also proves that the prover P knows the square root w (a witness) of y modulo x, meaning it is a zero-knowledge proof of knowledge. By interacting with the prover multiple times an extractor algorithm that runs in expected polynomial time is able to extract w from its interaction with P. Why does this not contradict that the protocol is perfect zero-knowledge?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The knowledge extraction algorithm has more power than a verifier who participates in the ZK interaction -- it can rewind time.
Consider a typical ZK protocol with 3 messages, where the prover sends the first one:
- Prover: send $M_1$ to verifier
- Verifier: send $M_2$ to prover
- Prover: send $M_3$ to verifier.
A typical knowledge extraction algorithm works by doing the following:
- Run the prover until it produces $M_1$
- Choose $M_2$ and give it to the prover
- Run the prover until it produces $M_3$
- Return the prover to the internal state it had after step 1
- Choose a different $M'_2$ and give it to the prover
- Run the prover until it produces $M'_3$
- From the combination of these values, compute the witness
You can think of the knowledge extraction algorithm as running the prover inside a virtual machine, and restoring the VM image to an earlier state -- from the perspective of the prover, rewinding time and attempting a different timeline.
A verifier cannot cause the same thing to happen in a typical interaction with the prover. Even if the verifier interacts with the prover multiple times, there is a subtle difference:
- Interact with the prover and receive $M_1$ from it
- Choose $M_2$ and give it to the prover
- Receive $M_3$ from the prover
- Ask the prover to prove the same thing again. This time, the prover sends $M'_1$
- Choose $M'_2$ and give it to the prover
- Receive $M'_3$ from the prover
The verifier sees two transcripts $(M_1, M_2, M_3)$ and $(M'_1, M'_2, M'_3)$, where $M_1$ and $M'_1$ are chosen independently (by the prover). But the knowledge extraction algorithm sees two transcripts $(M_1, M_2, M_3)$ and $(M_1, M_2', M_3')$ with the same $M_1$! The verifier cannot say "please prove the same thing again, and don't forget to use the same $M_1$ as last time" because the protocol instructs the prover to generate $M_1$ fresh for each interaction.
This is precisely the advantage that typical knowledge extraction algorithms use to extract the witness, and why the regular verifier cannot do the same thing. I recommend that you read about Schnorr's identification protocol, which is the simplest protocol whose extraction works in this way.
-
$\begingroup$ Thanks for the great explanation and the recommendation! $\endgroup$ Commented Jul 17 at 10:38