# Alternatives of how the Fiat-Shamir transform random oracle is applied to a protocol

The Fiat-Shamir transform typically works by substituting (public) coin tosses from the verifier by hashes of the prover's messages until this point, i.e.: $$H(x,\alpha_1) = \beta_1, \\ H(x,\alpha_1, \alpha_2) = \beta_2,\\H(x,\alpha_1, \alpha_2, \alpha_3) = \beta_3,\\\vdots$$ where $$x$$ is the public input of the protocol and the $$\alpha_i$$'s are the prover's messages.

I understand that this is proven to be secure in the random oracle model (at least for constant-round protocols), but I am looking for some alternatives to this paradigm. Namely, I want to know what happens if I substitute the inputs $$\alpha_1, \alpha_2, \alpha_3, ...$$ with a function of them. Being more specific, what would happen if instead of performing $$H(x,\alpha_1,\alpha_2,\dots,\alpha_i)$$ I perform $$H(x,f_i(\alpha_1,\alpha_2,\dots,\alpha_i))$$, where $$f_i$$ is a $$i$$-th variate function mapping the $$i$$-th dimensional uniform distribution to a $$j$$-th dimensional space, for each $$i$$.

Examples: If we take all the $$f_i$$ to be the identity function with $$j=i$$ (i.e., $$f_i(\alpha_1, \dots, \alpha_i) = (\alpha_1,\dots,\alpha_i)$$ then we get the original way of performing the Fiat-Shamir transform. Another (not known to be secure) example would be $$f_i(\alpha_1, \dots, \alpha_i) = \alpha_1 + 2\cdot\alpha_2 + \dots +i\cdot\alpha_i$$.

A more general question I ask to myself is: which conditions should the $$f_i$$ satisfy in order to ensure that the Fiat-Shamir transformed protocol is secure in the random oracle model.

Why this could be useful: Well, I have not come up with a proper motivation yet; but I think that it could be useful in the proof composition scenario. Namely, if I try to compute a non-interactive proof of a non-interactive proof then I have to represent the computation of each verifier's messages of the first proof in my computational model (say arithmetic circuits). The resulting would be much shorter if the has function has fewer inputs.

In fact, I have seen that some people implement the Fiat-Shamir as follows: $$H(x,\alpha_1) = \beta_1, \\ H(\beta_1, \alpha_2) = \beta_2,\\H(\beta_2, \alpha_3) = \beta_3,\\\vdots$$which is slightly different from the original definition. Is this proven to be secure?

1. Your last Fiat-Shamir scheme can be viewed as $$H(x, \alpha_1)$$, $$H(H(x, \alpha_1), \alpha_2)$$, $$H(H(H(x, \alpha_1), \alpha_2), \alpha_3), ...$$. If $$H$$ is a random oracle, this should have similar analysis to the first Fiat-Shamir transform you presented.
3. Taking into account points 1) and 2), for certain protocols, Fiat-Shamir may still be sound if your function $$f(\cdot)$$ is not a random oracle. However, this requires considerable care and proof.
• Very interesting paper, thank you. I think it would be of general interest knowing which properties $f$ should satisfy (and hope that they do not depend on the particular protocol). Oct 5, 2022 at 17:20