Forking lemma

Fix an integer and a set of size . Let be a randomized algorithm that on input returns a pair with and side output , and let be a randomized input generator. The accepting probability of is

The forking algorithm reruns on the same coins and the same first answers, with fresh answers from position on:

\begin{algorithm}
\algname{Algorithm}
\caption{$F_\calA(x)$}
\begin{algorithmic}
\State pick coins $\rho$ for $\calA$ uniformly at random
\State $h_1, \ldots, h_q \getsr H$
\State $(I, \sigma) \gets \calA(x, h_1, \ldots, h_q; \rho)$
\If{$I = 0$}
\Return $(0, \bot, \bot)$
\EndIf
\State $h'_I, \ldots, h'_q \getsr H$
\State $(I', \sigma') \gets \calA(x, h_1, \ldots, h_{I-1}, h'_I, \ldots, h'_q; \rho)$
\If{$I' = I$ and $h'_I \ne h_I$}
\Return $(1, \sigma, \sigma')$
\EndIf
\Return $(0, \bot, \bot)$
\end{algorithmic}
\end{algorithm}

With ,

which implies — BN06.

Proof

Fix and write , for the probabilities over the remaining coins. For , let be the probability over that . Given the two runs are independent, so , and by Cauchy–Schwarz

The fresh answer is independent of the first run, so and . Averaging over with gives the bound — BN06.

Application to Fiat–Shamir signatures

In a random-oracle proof for a Fiat–Shamir signature built from a sigma protocol, runs the forger, answers its th random-oracle query with , and returns the index of the query that fixes the challenge of a valid forgery, or , making that query itself if the forger did not. A successful fork gives two accepting conversations with a common commitment and distinct challenges, from which special soundness extracts a witness. For signatures from three-move honest-verifier zero-knowledge identification schemes with special soundness this is the proof of PS96 (ID ⇒ DS, DLOG ⇒ Schnorr signatures); by the bound above, a forger with success probability making oracle queries yields a witness with probability about — BN06.

For Schnorr signatures the time-to-success loss of the expected-time reduction of PS00 (see below) is essentially optimal: if OMDL is hard, every algebraic reduction from DLOG to Schnorr forgery in the random-oracle model loses a factor in the time-to-success ratio, where is close to as long as the forger’s success probability is noticeably smaller than , and a factor , independent of , when the reduction’s cost is measured by expected time and expected number of queries (barrier) — Seu12.

Variations

Pointcheval–Stern forking lemma

The original lemma concerns signatures of the form , where is random, is the random-oracle hash of , and depends only on , and . If an efficient forger given only public data outputs a valid signature with non-negligible probability, then with non-negligible probability a rerun with the same random tape and a different random oracle outputs two valid signatures and with — PS96. The lemma extends to chosen-message attacks when the triples can be simulated without the secret key — PS96. An exact-security version obtains the two signatures in expected time from a forger running in time with success probability and random-oracle queries, for above a threshold depending on , the number of signing queries and the length of the oracle’s answers — PS00.

Splitting lemma

Let with for independent and , and let be distributed as , independently of . For every , the set

satisfies and — PS00. Writing , the first bound follows from , the second from — standard.

Reset lemma

For a three-move public-coin protocol with challenge space , fix a prover and its input. Let be the probability that the verifier accepts, and the probability that running on fixed coins against two independent challenges yields two accepting conversations with . Then — BP02. The proof is the case of the argument above: when . Applied to the Schnorr identification protocol, it turns a passive impersonator with success probability into a DLOG solver with success probability at least (DLOG ⇒ Schnorr identification protocol) — BP02.

High-moment forking lemma

If DLOG is 2-moment hard, meaning that every algorithm’s success probability is bounded in terms of the second moment of its running time, as in the generic group model, a high-moment forking lemma for sigma protocols shows that every -time Schnorr forger making hash queries succeeds with probability at most in a group of prime order , against from earlier proofs — RS21.

Participates in

Used via Forking lemma