Forking Lemma

Lemma 1: The Splitting Lemma

Let  such that . For any  define

then the following statements hold:

3. .

: Assume that  Then

This implies a contradiction, hence the result 1.

Statement 2 is a straightforward consequence of the definition.

We finally turn to the last assertion, using Bayes' law:

No-Message Attacks

Lemma 2: The Forking Lemma

Assume that, within the time bound  produces, with probability  valid signature . Then, within time  and with probability replay of this machine outputs two valid signatures  and  such that 

:

We start with a no-message attacker  which is a probabilistic polynomial time Turing machine with random tape  During the attack, this machine asks a polynomial number of questions to the random oracle  We may assume that these questions are distinct: for instance,  can store questions and answers in a table.

Let  be the  distinct questions and let  be the list of the  answers of  It is clear that a random choice of  exactly corresponds to a random choice of  Then, for a random choice of  with probability  outputs a valid signature  Since  is a random oracle, it is easy to see that the probability for  to be equal to  is less than  unless it has been asked during the attack. (  is the security parameter and outputs of  are of size ) So, it is likely that the question  is actually asked during a successful attack.

Accordingly, we define  to be the index of this question:  (we let  if the question is never asked). We then define the sets

We call  the set of the successful pairs  and we note that the set  is a partition of . With those definitions, we find a lower bound for the probability of success, Let  be the set consisting of the most likely indices 

Lemma 3

: By definition of the sets  This probability is equal to  Since the complement of  contains fewer than  elements, this probability is at least . 

We now run the attacker  times with random  and random  Since  with probability greater than  we get at least one pair  in . It is easily seen that this probability is lower bounded by .

We now apply the Splitting-lemma (lemma 1) for each integer  we denote by  the restriction of  to queries of index strictly less than  Since  there exists a subset  of executions such that,

Since all the subsets  are disjoint,

We let  denote the index  corresponding to the successful pair. With probability at least  and 

Consequently, with probability greater than  the  attacks have provided a successful pair  with  and 

Furthermore, if we replay the attack, with fixed  but randomly chosen oracle  such that  we know that  Then

where  and  We thus replay the attack  times with a new random oracle  such that  With probability greater than  we get another success.

Finally, after less than  repetitions of the attack, with probability greater than  we have obtained two valid signatures  and  with  and distinct challenges  

Adaptively Chosen-Message Attacks

Lemma 4 : The Forking Lemma

Assume that, within a time bound  produces, with probability  a valid signature    is the number of queries that  can ask to the signer. If the triples  can be simulated without knowing the secret key, with an indistinguishable distribution probability, then, a replay of the attacker  where interactions with the signer are simulated, outputs two valid signatures  and  such that  within time  and with probability 

: As in the previous proof, we let  denote the  distinct queries to the random oracle,  the respective answers, and  the  queries (possibly all the same) to the signing oracle.

Using the simulator, we can simulate the answers of the signer without knowledge of the secret key. For a message  the simulator answers a triple  Then, the attacker assumes that  and stores it.

The previous proof can be exactly mimicked, except for the problem added by the simulations: there is some risk of "collisions" of queries, or supposed queries, to the random oracle. Recall that in the definition of generic digital signature schemes, we made the assumption that the probability for a "commitment"  to be output by the signing oracle is less than  Then, two kinds of collisions can appear:

• A pair  that the simulator outputs also appears in the list of questions asked to the random oracle by the attacker (some question  ). The probability of such an event is less than .
• A pair  that the simulator outputs is exactly similar to another pair produced by this simulator (some question  The probability of such an event is less than .

Altogether, the probability of collisions is less than  Therefore,

This is clearly greater than  We can then apply the previous Forking Lemma (lemma 2). Such a replay succeeds with probability  within time