Forking Lemma - Statement of The Lemma

Statement of The Lemma

The generalized version of the lemma is stated as follows. Let A be a probabilistic algorithm, with inputs (x, h₁, ..., h_q; r) that outputs a pair (J, y), where r refers to the random tape of A (that is, the random choices A will make). Suppose further that IG is a probability distribution from which x is drawn, and that H is a set of size h from which each of the h_i values are drawn according to the uniform distribution. Let acc be the probability that on inputs distributed as described, the J output by A is greater than or equal to 1.

We can then define a "forking algorithm" F_A that proceeds as follows, on input x:

1. Pick a random tape r for A.
2. Pick h₁, ..., h_q uniformly from H.
3. Run A on input (x, h₁, ..., h_q; r) to produce (J, y).
4. If J = 0, then return (0, 0, 0).
5. Pick h'_J, ..., h'_q uniformly from H.
6. Run A on input (x, h₁, ..., h_J−1, h'_J, ..., h'_q; r) to produce (J', y').
7. If J' = J and h_J ≠ h'_J then return (1, y, y'), otherwise, return (0, 0, 0).

Let frk be the probability that F_A outputs a triple starting with 1, given an input x chosen randomly from IG. Then