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?
For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted into a key recovery attack.

The technical question is how can you make sure that the forger is going to comply to our expectations and really forge two signatures for the same randomness. Indeed, in general, nothing forces the adversary to use its randomness in a simple way. In particular, giving him the same coins and forcing changes the messages is not going to achieve the desired goal, because the adversary is allowed to mix the messages themselves into the randomness used for signing.

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).
$$

The proof given by Bellare and Neven is not too hard to follow and I would recommend reading it.