Forking lemma

Forking lemma

The forking lemma is any of a number of related lemmas in cryptography research. The lemma states that if an adversary (typically a probabilistic Turing machine), 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. [Ernest Brickell, David Pointcheval, Serge Vaudenay, and Moti Yung, " [ Design Validations for Discrete Logarithm Based Signature Schemes] ", Third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Australia, January 18–20, 2000, pp. 276–292.] Adam Young and Moti Yung, "Malicious Cryptography: Exposing Cryptovirology", Wiley press, 2004, pp. 344.] In their paper, the forking lemma is specified in terms of an adversary that attacks a digital signature scheme instantiated in the random oracle 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. [David Pointcheval and Jacques Stern, " [ Security Proofs for Signature Schemes] ", Advances in Cryptology — EUROCRYPT '96, Saragossa, Spain, May 12–16, 1996, pp. 387–398.] The forking lemma was later generalized by Mihir Bellare and Gregory Neven.Mihir Bellare and Gregory Neven, " [ Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma] ", Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS), Alexandria, Virginia, 2006, pp. 390–399.] The forking lemma has been used to prove the security of a variety of digital signature schemes and other random-oracle based cryptographic constructions.

tatement of the lemma

The generalized version of the lemma is stated as follows. Let "A" be a probabilistic algorithm, with inputs ("x", "h"1, ..., "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 "hi" 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" "FA" that proceeds as follows, on input "x":
# Pick a random tape "r" for "A".
# Pick "h"1, ..., "h""q" uniformly from "H".
# Run "A" on input ("x", "h"1, ..., "h""q"; "r") to produce ("J", "y").
# If "J" = 0, then return (0, 0, 0).
# Pick "h'J, ..., h'q" uniformly from "H".
# Run "A" on input ("x", "h"1, ..., "h""J"−1, "h"'"J", ..., "h"'"q"; "r") to produce ("J"', "y"').
# If "J' " = "J" and "hJ" ≠ "h'J" then return (1, "y", "y"'), otherwise, return (0, 0, 0).

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

: ext{frk} geq ext{acc} cdot left ( frac ext{acc}{q} - frac{1}{h} ight).


The idea here is to think of "A" as running two times in related executions, where the process "forks" at a certain point, when some but not all of the input has been examined. In the alternate version, the remaining inputs are re-generated but are generated in the normal way. The point at which the process forks may be something we only want to decide later, possibly based on the behavior of "A" the first time around: this is why the lemma statement chooses the branching point ("J") based on the output of "A". The requirement that "hJ" ≠ "h'J" is a technical one required by many uses of the lemma. (Note that since both "hJ" and "h'J" are chosen randomly from "H", then if "h" is large, which would be normal, the probability of the two values not being distinct is extremely small.)


For example, let "A" be an algorithm for breaking a digital signature scheme in the random oracle model. Then "x" would be the public parameters (including the public key) "A" is attacking, and "hi" would be the output of the random oracle on its "i"th distinct input. The forking lemma is of use when it would be possible, given two different random signatures of the same message, to solve some underlying hard problem. An adversary that forges once, however, gives rise to one that forges twice on the same message with non-negligible probability through the forking lemma. When "A" attempts to forge on a message "m", we consider the output of "A" to be ("J", "y") where "y" is the forgery, and "J" is such that "m" was the "J"th unique query to the random oracle (it may be assumed that "A" will query "m" at some point, if "A" is to be successful with non-negligible probability). (If "A" outputs an incorrect forgery, we consider the output to be (0, "y").)

By the forking lemma, the probability ("frk") of obtaining two good forgeries "y" and "y' " on the same message but with different random oracle outputs (that is, with "hJ ≠ h'J") is non-negligible when "acc" is also non-negligible. This allows us to prove that if the underlying hard problem is indeed hard, then no adversary can forge signatures.

This is the essence of the proof given by Pointcheval and Stern for a modified ElGamal signature scheme against an adaptive adversary.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • Pointcheval-Stern signature algorithm — In cryptography, the Pointcheval Stern signature algorithm is a digital signature scheme based on the closely related ElGamal signature scheme. It changes the ElGamal scheme slightly to produce an algorithm which has been proven secure in a… …   Wikipedia

  • Jacques Stern (Kryptologe) — Jacques Stern (* 21. August 1949 in Paris) ist ein französischer Kryptologe, Informatiker und Mathematiker. Jacques Stern Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Glossary of botanical terms — Many of the terms used in Wikipedia glossaries (often most) are already defined and explained within Wikipedia itself. However, lists like the following indicate where new articles need to be written and are also useful for looking up and… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • Projet:Médecine/Index — Articles 0 9 1,2 dibromo 3 chloropropane · 112 (numéro d urgence européen) · 1935 en santé et médecine · 1941 en santé et médecine · 1er régiment médical · 2 iodothyronine déiodinase · 2,4,6 trichlorophénol · 2005 en santé et médecine · 2006 en… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”