What is a "rewinding argument"?

Question

I've been reading a bit about cryptographic protocols and I keep seeing the phrase "rewinding argument". I've been unable to find a good source that would explain what is meant by this. It seems like proofs that use this technique cause trouble against active adversaries? I would appreciate if someone would explain what a rewinding argument is and why this is the case.

Answer 1

Rewinding is used in all sorts of interactive protocols, but it's perhaps easiest to understand it for a zero-knowledge property.

In proving zero-knowledge, we consider a cheating verifier interacting with an honest prover. The prover knows something that the verifier doesn't (say, the factorization of an RSA modulus), and we worry that by cheating, the verifier could gain some information.

The zero-knowledge property means that "whatever the verifier outputs from this interaction, he could have generated without interacting at all". If that's true, then the interaction must not have conveyed any meaningful "knowledge" to the verifier.

So how do we prove the statement in quotes? We say: first suppose you have a cheating verifier $V$. When $V$ talks to an honest prover, it outputs (a distribution of) some transcript $t$. We have to show how to sample the same (or very close) distribution of $t$, without talking to any honest prover. It's not likely that we can analyze the code of $V$ to "figure out what it's doing." Instead, we have to treat $V$ as a kind of black-box. Recall that $V$ is designed to operate in an interactive fashion, so we have to feed protocol messages into $V$, pretending to be the honest prover.

We might feed into $V$ a simulated "message 1" from the prover, and then later a simulated "message 2". Then, after seeing how $V$ responded, we might go back to a previous internal state of $V$ and feed in a different simulated "message 2" -- that's rewinding. We can rewind and invoke $V$ many different times, as long as we are careful to spend only polynomial time overall (assuming $V$ itself is polynomial-time).

BTW, there are some security frameworks (e.g., Universal Composability) which do not allow rewinding.

Answer 2

The short version is: a "rewinding argument" is a proof technique used to demonstrate the security of a zero-knowledge proof (i.e., to show that an interactive protocol is zero-knowledge). Rewinding arguments can be used to show soundness, or to show that the zero-knowledge property is met.

For more details, see PulpSpy's answer to another question (as PulpSpy suggests). Or, read any introductory reference on zero-knowledge proofs. Rewinding is a fundamental technique for proving the security of zero-knowledge proofs, so it should be covered in any good introduction to the subject.