# Second challenge in Fiat-Shamir for 5-round schemes

I'm not sure how to compute the second challenge when applying FS to a 5-round protocol. I've seen TWO different formulas (with and without including the first challenge) and don't know which one is correct.

Suppose we have 5-round interactive protocol for some statement $$st$$:

$$P$$$$V$$: $$x$$ means prover sent $$x$$ to verifier.

$$P$$$$V$$: $$y$$ means verifier sent $$y$$ to prover.

1. $$P$$$$V$$: $$\alpha_1$$ // 1st commitment
2. $$P$$$$V$$: $$ch_1$$ // 1st challenge
3. $$P$$$$V$$: $$\alpha_2$$ // 1st answer
4. $$P$$$$V$$: $$ch_2$$ // 2nd challenge
5. $$P$$$$V$$: $$\alpha_3$$ // 2nd answer

Now we can apply Fiat-Shamir transform to get a non-interactive proof.

Question: how we compute $$ch_2$$?:

a) $$ch_2 = Hash(st|\alpha_1|\alpha_2|aux)$$

b) $$ch_2 = Hash(st|\alpha_1|\alpha_2|ch_1| aux)$$ ← includes $$ch_1$$

On the one hand, $$ch_2$$ should be independent of $$ch_1$$, right? An original article of Pointcheval and Stern[2], article by Kiltz et. al[1], plus some answers here use formula a.

On the other hand, there are articles [3],[4] where the formula b is used.

UPD: Will the fact of whether $$ch1$$ included or not matter for the Forking Lemma?

[1] Tightly-Secure Signatures from Five-Move Identification Protocols by Eike Kiltz, Julian Loss, and Jiaxin Pan https://eprint.iacr.org/2017/870.pdf

[2] Security Arguments for Digital Signatures and Blind Signatures by David Pointcheval and Jacques Stern https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf

[3] From 5-pass MQ-based identification to MQ-based signatures by Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe https://eprint.iacr.org/2016/708.pdf

[4] Extended Security Arguments for Signature Schemes by Sidi Mohamed El Yousfi Alaoui, Özgür Dagdelen, Pascal Véron, DavidGalindo, Pierre-Louis Cayrel https://hal.inria.fr/hal-00684486/document

These are equivalent. Given that the first challenge is a deterministic function of the statement and $$\alpha_1$$, it makes no difference. What is crucial is just to include the statement, and the entire transcript to that point. (Note that anything that is deterministically dependent on other things doesn't have to be included in the transcript.)
• It should not matter. If you are rewinding back behind $\alpha_2$ then you can change $ch1$ anyway, and if you are rewinding to after $\alpha_2$ then you can change $ch2$ anyway (since you are running the random oracle). Feb 6, 2020 at 15:10