Forking lemma

Forking lemma

The forking lemma is any of a number of related <a href="/en/Lemma_(mathematics)" title="Lemma (mathematics)" class="wl">lemmas</a> in <a href="/en/Cryptography" title="Cryptography" class="wl">cryptography</a> research. The lemma states that if an adversary (typically a <a href="/en/Probabilistic_Turing_machine" title="Probabilistic Turing machine" class="wl">probabilistic Turing machine</a>), on inputs drawn from some <a href="/en/Probability_distribution" title="Probability distribution" class="wl">distribution</a>, produces an output that has some property with <a href="/en/Negligible_function" title="Negligible function" class="wl">non-negligible</a> <a href="/en/Probability" title="Probability" class="wl">probability</a>, then with non-negligible probability, if the adversary is re-run on new inputs but with the same random tape, its second output will also have the property.

This concept was first used by <a href="/en/David_Pointcheval" title="David Pointcheval" class="wl">David Pointcheval</a> and <a href="/en/Jacques_Stern" title="Jacques Stern" class="wl">Jacques Stern</a> in "Security proofs for signature schemes," published in the proceedings of <a href="/en/Eurocrypt" title="Eurocrypt" class="mw-redirect wl">Eurocrypt</a> 1996.<a href="#cite_note-1" style="counter-reset: mw-Ref 1;">[1]</a><a href="#cite_note-YoungYung-2" style="counter-reset: mw-Ref 2;">[2]</a> In their paper, the forking lemma is specified in terms of an adversary that attacks a <a href="/en/Digital_signature" title="Digital signature" class="wl">digital signature</a> scheme instantiated in the <a href="/en/Random_oracle" title="Random oracle" class="wl">random oracle</a> model. They show that if an adversary can forge a signature with non-negligible probability, then there is a non-negligible probability that the same adversary with the same random tape can create a second forgery in an attack with a different random oracle.<a href="#cite_note-3" style="counter-reset: mw-Ref 3;">[3]</a> The forking lemma was later generalized by <a href="/en/Mihir_Bellare" title="Mihir Bellare" class="wl">Mihir Bellare</a> and Gregory Neven.<a href="#cite_note-BellareNeven-4" style="counter-reset: mw-Ref 4;">[4]</a> The forking lemma has been used and further generalized to prove the security of a variety of digital signature schemes and other random-oracle based cryptographic constructions.<a href="#cite_note-YoungYung-2" style="counter-reset: mw-Ref 2;">[2]</a><a href="#cite_note-5" style="counter-reset: mw-Ref 5;">[5]</a><a href="#cite_note-6" style="counter-reset: mw-Ref 6;">[6]</a>

The forking lemma is any of a number of related lemmas in cryptography research.  The lemma states that if an adversary , on inputs drawn from some distribution, produces an output that has some property with non-negligible probability, then with non-negligible probability, if the adversary is re-run on new inputs but with the same random tape, its second output will also have the property. This concept was first used by David Pointcheval and Jacques Stern in "Security proofs for signature schemes," published in the proceedings of Eurocrypt 1996. 