4
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Bean Guy
    Oct 5, 2022 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.