= Rewinding in cryptographic proofs
\b[Rewinding in cryptographic proofs] is a simulation or extraction technique that returns an algorithmic participant to an earlier state and explores another continuation. The saved state includes the relevant earlier messages and randomness. The technique is justified by the simulator's or extractor's access in the mathematical model; it is not an extra power of the ordinary verifier during a live exchange.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Section2.2.1, general-verifier simulation and repeated continuations, printedpp.27–28]{ref}
For the <graph-isomorphism proof protocol>, two accepting continuations of the same first message can answer different challenge bits. A <knowledge extractor> can combine their response mappings to obtain a <cryptographic witness>. If the prover instead starts again with a different first message, the responses need not combine in that way.
An original retry calculation explains an efficiency condition. Suppose independent simulation attempts succeed with probability $q$ and each failed attempt returns to the required earlier state. The attempt count $T$ has a <geometric distribution>:
$$
\Pr(T=t)=(1-q)^{t-1}q,\qquad
\mathbb E[T]=\frac1q.
$$
At $q=1/2$, the expected number of attempts is2; at $q=1/100$, it is100. Constant or inverse-polynomial success can therefore support expected <polynomial time>, whereas exponentially rare success generally cannot.
A valid argument must also account for the cost of each attempt and show that the resulting output distribution is correct. Restoring a state, conditioning on success and restarting an entire protocol are distinct operations.
Back to article page
