# Fiat-Shamir paradigm and the forking lemma

I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also mentioned that the same proof idea works for showing the Fiat-Shamir transformed interactive proof system is sound in the random oracle model.

I am not sure I understand why the forking lemma implies the Fiat-Shamir transformed noninteractive protocol is sound using a random oracle, or it is essential to apply it for only the soundness. There are many papers about instantiation in the plain model, but that is beyond what I am trying to understand for now.

It would be appreciated if anyone could explain the connection, or point some good references about that.

• I don't understand what the question is. Fiat-Shamir, Pointcheval-Stern, and Bellare-Neven are good references. You use the interactive-to-non-interactive transform of Fiat-Shamir to make the interactive protocol non-interactive. The question arises, is it secure? Completeness and Zero-knowledgeness are not affected. The proof technique of Pointcheval and Stern shows that the transformed protocol has (knowledge-)soundness as well. How secure is it? The analysis Bellare-Neven gives you a concrete number. – Alan Dec 8 '18 at 16:14
• My question is that why the forking lemma implies soundness when applying Fiat-Shamir transformation. The forking lemma seems to say that if the transcripts from 2 different random oracles agrees on the first few points, then if the adversary knows where to fork, then he has an attack to some signature scheme. I am not sure why this implies the transformed interactive proof system is sound. – user50394 Dec 9 '18 at 21:39

Let's recall important definitions. A proof system $$(\mathsf{P}, \mathsf{V})$$ for an NP language $$\mathcal{L}$$ is a pair of interactive Turing machines where the prover ($$\mathsf{P}$$) and the verifier ($$\mathsf{V}$$) receive a common input $$\ell \in \{0,1\}^*$$ and the prover receives an additional input $$w \in \{0,1\}^*$$ that is the witness for $$\ell$$, i.e., the relation $$\mathcal{R}_\mathcal{L}$$ defined by the NP language $$\mathcal{L}$$ satisfies $$\mathcal{R}_\mathcal{L}(\ell,w) = 1$$. The prover and verifier exchange a couple of messages and finally the verifier outputs a single bit denoted by $$\mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w)\leftrightarrow\mathsf{V}(\ell)\rangle)$$, indicating whether the verifier accepts the proof (1) or rejects it (0). The proof system is public-coin if the verifier's messages consist of pure, unprocessed randomness. In this case the Fiat-Shamir heuristic says that no security is lost by replacing these randomly chosen messages by the hash of all messages up until that point. (And since there is a proof of this fact, albeit in the random oracle model, it is technically wrong to refer to it as a heuristic --- hence the more common phrase "Fiat-Shamir transform".)

The proof system is complete for a language $$\mathcal{L} \in$$ NP if honest provers are likely to succeed, i.e., $$\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathrm{Pr}[\mathcal{R}_\mathcal{L}(\ell,w) = 1 \, \Rightarrow \, \mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1] \geq 1 - \mathsf{negl}(\lambda)$$, for some function $$\mathsf{negl}(\lambda)$$ that is negligible in the security parameter.

The proof system is zero-knowledge if the transcript, i.e., the list of all exchanged messages which is denoted by $$\langle\mathsf{P}(\ell,v) \leftrightarrow \mathsf{V}(\ell)\rangle$$, is indistinguishable from the output of some simulator $$\mathsf{S}$$ that receives the string $$\ell$$ but not the witness $$w$$. Formally, $$\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathcal{R}_\mathcal{L}(\ell, w) = 1 \, \Rightarrow \, \langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle \sim \mathsf{S}(\ell)$$. Here $$\sim$$ denotes your favorite notion of indistinguishability of probability distributions, i.e., perfect, statistical, or computational.

With respect to soundness, it is important to draw a clear distinction between two related notions. First, the proof system has plain soundness if no (appropriately bounded) adversary $$\mathsf{A}$$ can make the verifier accept nonmembers of the language: $$\forall n \not \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle \mathsf{A}(n) \leftrightarrow \mathsf{V}(n)\rangle) = 1] \leq \mathsf{negl}(\lambda)$$. I call this notion plain soundness for the sake of exposition but the literature refers to it simply as soundness. Second, the proof system has knowledge-soundness if there is an (appropriately efficient) extractor machine $$E$$ that can extract and output a valid witness from any successful proof-forger $$\mathsf{B}$$, whether it receives the witness $$w$$ or not. Formally, $$\forall \ell \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle\mathsf{B}(\ell) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1 \, \Rightarrow \, \mathcal{R}_\mathcal{L}(\ell, \mathsf{E}^\mathsf{B}()) = 1] \geq \mathsf{noti}(\lambda)$$, where $$\mathsf{noti}(\lambda)$$ is some noticeable function of the security parameter. Here $$\mathsf{E}^\mathsf{B}$$ means that the algorithm $$\mathsf{E}$$ has black-box access to $$\mathsf{B}$$, meaning that $$\mathsf{E}$$ is allowed to interact with $$\mathsf{B}$$ through messages that have the format of the proof system but $$\mathsf{E}$$ is not allowed to view or alter $$\mathsf{B}$$'s state. The literature also refers to this notion as witness-extractability and, confusingly, as soundess. Proof systems with this property are proofs of knowledge.

For many languages, knowledge-soundness is the relevant property and plain soundness is not. Consider for instance the standard Schnorr proof of knowledge of a discrete logarithm, whereby knowledge of an exponent $$x \in \mathbb{Z}_{|\mathbb{G}|}$$ is proven such that exponentiation-by-$$x$$ sends $$g \in \mathbb{G}$$ to $$X = g^x \in \mathbb{G}$$. When $$g$$ is a generator, as it usually is, plain soundness is trivial: since $$X$$ is a group element it must have a discrete logarithm with respect to $$g$$. However, for circuit-satisfiability type languages, plain soundness is usually more important than knowledge-soundness.

To prove plain soundness, it suffices to count the number of possible challenges from the verifier that expose a cheating prover; and the number of possible challenges that allow him to get away with the fraud. The ratio between the number of challenges that do not expose the cheating prover and the total number is known as the soundness error --- the fact that the verifier chooses his challenges at random makes this ratio equal the cheating prover's success probability and if it is negligible in the security parameter then plain soundness is satisfied. With the Fiat-Shamir transform, it suffices to argue from the difficulty of finding particular preimages to the random oracle. Formally, you can model the (classical) random oracle as a procedure that samples a random output only when it is needed and no sooner. Then the only way to find an input that leads to an answerable challenge is to test enough of them.

To prove knowledge-soundness, one must provide a description for the witness-extractor $$\mathsf{E}$$ and show that its success probability is noticeable if $$\mathsf{B}$$ has a noticeable success probability of convincing the verifier. The Forking Lemma provides such a description:

1. $$\mathsf{E}$$ plays the part of $$\mathsf{V}$$ honestly and runs the protocol with $$\mathsf{B}$$ thereby obtaining one transcript $$T_1$$.
2. $$\mathsf{E}$$ rewinds $$\mathsf{B}$$ to just after one of its messages, typically where it commits to something.
3. Once again, $$\mathsf{E}$$ plays the part of $$\mathsf{V}$$ honestly but with different randomness, thereby obtaining a second transcript $$T_2$$.

The language is structured in such a way that it is easy to extract a witness from two valid transcripts with the same commitments but different challenges. This description involves only one instance of rewinding; it may be necessary to rewind multiple times to obtain a set of transcripts satisfying very particular constraints.

Intuitively, the success probability of the extractor $$\mathsf{E}$$ should be somehow related to the success probability of the proof-forger $$\mathsf{B}$$. However, Bellare and Neven show that there is necessarily a square-root security degradation. In particular, if the extractor $$\mathsf{E}$$ splits into 2 branches, then $$\mathrm{Pr}[\mathsf{B} \, \mathit{success}] \leq \sqrt{\mathrm{Pr}[\mathsf{E} \, \mathit{success}]}$$, because the proof-forger $$\mathsf{B}$$ has to be successful in both branches. This means that even if the discrete logarithm problem takes $$2^{128}$$ units of work to compute, the proof shows only that the adversary as to perform at least $$2^{64}$$. In general, if the extraction requires $$b$$ branches, then the proof technique will induce a $$b$$th root degradation.

With the Fiat-Shamir transform, the random messages from the verifier are replaced with the response from the random oracle upon being queried with the list of protocol messages up until that point. This random oracle is simulated by the extractor $$\mathsf{E}$$, meaning that it can choose which responses the random oracle will provide. The trick is that by rewinding the proof-forger $$\mathsf{B}$$, the extractor $$\mathsf{E}$$ can reprogram different outputs for the random oracle. In particular, the extractor $$\mathsf{E}$$ proceeds as follows.

1. $$\mathsf{E}$$ runs $$\mathsf{B}$$ and provides it access with a random oracle $$\mathsf{RO}$$ whose responses are sampled uniformly at random when they are needed, and obviously conformant to the responses of previous queries. This provides the extractor $$\mathsf{E}$$ with the first transcript $$T$$.
2. $$\mathsf{E}$$ rewinds $$\mathsf{B}$$ to just after one of its messages, typically where it commits to something. Note that the list of all messages up until this point is fixed; denote this list by $$L$$.
3. $$\mathsf{E}$$ replays $$\mathsf{B}$$ again from this point but provides it with access to a random oracle $$\mathsf{RO}'$$ whose only difference is its response to $$L$$. In particular, this response has been sampled at random. This second execution of $$\mathsf{B}$$ provides $$\mathsf{E}$$ with the second transcript $$T_2$$.

With $$T_1$$ and $$T_2$$, the extractor $$\mathsf{E}$$ should be able to extract the witness. If more transcripts are needed then the extractor rewinds and replays the proof-forger as often as necessary.

Well, at first, forking lemma helps to prove that if interactive protocol IP is sound, than it's Fiat-Shamir transformation FS(IT) is a sound non-interactive protocol.

Sot it's just shows that soundness preserves after applying Fiat-Shamir transformation. Soundness doesn't appear from nothing.

How exactly it helps? It's applied for such IP which are specially-sound, which means that: 2 transcripts with the same commitment but different challenges lead to revealing the secret (witness). Obviously, for interactive protocol, special-soundness implies soundness (which is another property of a protocol, by definition meaning that having black-box access to prover, including all inputs/outputs, you can extract the secret witness). Indeed: you just run the 2 copies of the prover (you can do this having black-box access) with different challenges; since IP is specially-sound, these 2 obtained transcripts reveal you a secret, so you're able to get a secret from blackbox access to the prover!

Well, moving to non-interactive FS(ID). Now, you can't just run prover 2 times with different challenges, because you just don't allow to choose challenges! The prover now chooses challenges using random oracle. Forking lemma helps us to show that you, as an attacker which has black-box access to the prover, can obtain 2 transcripts with the same commitment but different challenges by manipulating random-oracle responses. Note, that you can manipulate the random-oracle which prover uses, because you have black-box access to the prover and you emulates its working environment.