# understanding forking lemma

Every time when I read a paper that has digital signature, when it comes to prove the security of a digital signature scheme, many chances that the author will use the forking lemma.

The forking lemma says as follows:

Let $\mathcal A$ be a probabilistic polynomial time turing machine, given only the public data as input. If $\mathcal A$ can find, with non-negligible probability, a valid signature $(m,\sigma_1,h,\sigma_2)$, then with non-negligible probability, a replay of this machine, with the same random tape and a different oracle, outputs two signatures $(m, \sigma_1,h,\sigma_2)$ and $(m, \sigma_1,h',\sigma_2')$ such that $h$ is not equal to $h'$.

This wording comes from David Pointcheval and Jacques Stern's paper on "Security Proofs for Signature Schemes". They also give a proof to this lemma, but it's very difficult for me to read.

In order to understand what I'm saying, you can see an example of that on this paper "A Secure and Efficient Authenticated Diffie–Hellman Protocol" from page 8-9. It's a security proof about FXCR. You can download it from http://eprint.iacr.org/2009/408.pdf.

The forking lemma really puzzled me for a long time; who can give a simple way to understand it?

-

The key idea is to restart the adversary with the same randomness let it run without change until it generates the message $M_0$ that was signed in the first run together with its rzndomness and then force a change on the rest of the run. At this point, in a practical setting, you could imagine using a fault attack on the hash function. However, in a theoretical model, the change is achieved by changing the responses of the random oracle that models the hash function on the first query that involves $M_0$ and all subsequent queries.
When you do that, you already know the behavior of the adversary until $M_0$ is generated and hope that it will forge again on $M_0$ with the same randomness but a different hash value. This is where the forking lemma comes into play (for a general version, see Multi-signatures in the plain public-key model and a general forking lemma by Bellare and Neven http://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf). In this general version, it is a technical lemma that analyzes the behavior of an adversary that receives some random values (each taken uniformely from at set of $h$ elements) and outputs a pair of values $(J,\sigma)$ with $0\leq J\leq q$ when several runs with inputs sharing a common prefix are performed. Note that when $J=0$, the adversary is considered to fail. The result of the forking lemma is that the probability of getting two related runs with the same value of $J$ and a common prefix of length $J-1$ is not too small. More precisely, if $acc$ denotes the probability of success of an adversary on a random input and $frk$ the probability of getting two related runs as above then: $$frk\geq acc\cdot \left(\frac{acc}{q}-\frac{1}{h}\right).$$