15
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Do you have some examples where this phrase is used? $\endgroup$ Commented Sep 11, 2012 at 18:08
  • 1
    $\begingroup$ E.g. page 2 here: eprint.iacr.org/2008/163 $\endgroup$
    – Jaska
    Commented Sep 11, 2012 at 18:42
  • 2
    $\begingroup$ It is a little long, but I illustrate it in my answer to another question here: crypto.stackexchange.com/a/1412/64 $\endgroup$
    – PulpSpy
    Commented Sep 11, 2012 at 19:24

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ My question is if the verifier who is rewinded knows this, and he/she may respond maliciously to the queries after rewind. By this, he may prevent you to benefit from rewinding. right? $\endgroup$
    – A.Solei
    Commented Dec 22, 2023 at 14:08
  • $\begingroup$ When you rewind the adversary and give different inputs, the adversary's behavior might change. Your analysis / security proof needs to take this into account. $\endgroup$
    – Mikero
    Commented Dec 22, 2023 at 15:54
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It's also used to show soundness (for arguments and/or knowledge extraction). $\hspace{1.1 in}$ $\endgroup$
    – user991
    Commented Sep 15, 2012 at 7:27
  • $\begingroup$ Thanks, @RickyDemer. You have a good point: rewinding arguments can be used in showing soundness of other interactive arguments / proofs of knowledge (it is not limited to just zero-knowledge proofs). In my defense, I did mention in my answer that "rewinding arguments can be used to show soundness", but I appreciate your reminder that this applies more broadly than zero-knowledge proofs. That's a great point. $\endgroup$
    – D.W.
    Commented Sep 15, 2012 at 7:56
  • $\begingroup$ Oh, yeah, I somehow missed that you mentioned soundness. $\;$ $\endgroup$
    – user991
    Commented Sep 15, 2012 at 9:51

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.