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

in flag

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?

se flag

There are several points:

  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.
  2. Depending on the protocol, a random oracle may not be necessary for the Fiat-Shamir transform. For example, a recent work, Does Fiat-Shamir Require a Cryptographic Hash Function?, shows that the Fiat-Shamir transform remains sound even when instantiated using non-cryptographic hash functions (such as sum-mod-p or bit-decomposition). Important: This is for certain protocols!
  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.

Hopefully, this gets you a start!

Bean Guy avatar
in flag
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).

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.