states that If a PPT adversary with a random tape and a random oracle $O$, is able to produce a forgery/break a scheme with non-negligible probability, then it can break the scheme again with same random tape and different random oracle with non-negligible probability.

What input and output does A take?

$A:⟨x,(h_{1},…,h_{q});r⟩→(i,y)$ where $x$ is the input to the scheme, $h_{1},…,h_{q}$ denotes oracle queries, and $r$ is the random tape that is used to generate randomness for $A$.

A outputs index $i$ and forgery $y$.

What does the index $i$ represents?

When $i≥1$, it means that $A$ was able to successfully produce a forgery for a scheme.

Does the input to A gets changed?

What does the random tape do? Why is it same in both scenarios?

Let $A:⟨x,(h_{1},…,h_{q});r⟩→(i,y)$ where $x$ is the input to the scheme, $h_{1},…,h_{q}$ denotes oracle queries, and $r$ is the random tape that is used to generate randomness for $A$, and outputs $(i,y)$. Let $acc$ be the probability that $A$ is able to output $i≥1$.^{1}

Let’s define Forking algorithm $F_{A}$:

Pick a random tape $r$ for $A$.

Pick h_{1},\dots,h_{q} \xleftarrow{\}H$.

Run adversary on inputs to get outputs $i,y$.

If $i=0$, output $(0,0,0)$, halt. This means adversary was not able to break the scheme.

Pick h'_{i},\dots,h'_{q} \xleftarrow{\}H$

Run $A:(x,(h_{1},…,h_{i−1},h_{i},…,h_{q});r)→(i_{′},y_{′})$.

If $i_{′}=i$ and $y_{′}=y$, then output $1,y,y_{′}$. This means if $A$ was able to break the scheme at same index, with a different forgery, then output the two forgeries.

Let $frk$ denote probability that $F_{A}$ will output $(1,⋅,⋅)$, then $frk=acc⋅(qacc −h1 )$.

The index $i$ can be thought as a fork in the algorithm, where probability that some of initial inputs and $i_{th}$ query remains same is denoted by $acc$, then adversary re-generates the inputs after the branching point, but are generated from some random oracle.

More intuitively, $A$ can be thought as probabilistic algorithm that uses adversary $B$ to create forgery for a signature algorithm. Now, on input $x=m$, $A$ simulates random oracle $RO$ for $B$, and answers its queries the first time honestly, sampling $h_{1},…,h_{q}$ uniformly from set $H$. $B$ is able to output a forged signature for input. Now, $A$ rewinds $B$ to $i_{th}$ index, and simulate a random oracle $RO_{′}$ for the rest of the run. If $B$ outputs another forged signature $y_{′}$, then $A$ is successful.