# Fiat-Shamir with interactions

Suppose we have a standard $$\Sigma$$-protocol for proving the knowledge of a witness $$x$$ for the statement $$y$$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to get an interactive $$\Sigma'$$-protocol in ROM:

1. The prover $$\mathcal{P}$$ compute $$a$$ exactly like in $$\Sigma$$-protocol and sends it to the verifier $$\mathcal{V}$$.
2. The verifier $$\mathcal{V}$$ replies with a challenge $$e$$. So far, everything is like in $$\Sigma$$-protocol.
3. Modification: The prover $$\mathcal{P}$$ computes $$e' = \textsf{Hash}(e)$$ and uses $$e'$$ as the challenge to compute the answer $$z$$.

Has anyone seen this construction mentioned anywhere? I think it should have full ZK in ROM, but I never saw anything similar. Is it because $$\Sigma'$$ is folklore/not very useful, or am I wrong about the full ZK?

• So your goal is taking a $\Sigma$-protocol that is only known to be HVZK and making it ZK? May 1 at 20:59
• Yes, interactive protocol with ZK in ROM by just hashing the challenge before applying it. I just wonder if anyone was looking into something similar May 3 at 7:16

For the Fiat-Shamir transform, HVZK becomes ZK because the verifier sends nothing to the prover. The ZK simulator generates $$(a,e,z)$$ from the HVZK simulator and reprograms the oracle so that $$H(a)=e$$. This works because $$c$$ is uniformly random and the verifier cannot have known the value of $$H(a)$$ before the reprogramming (except with negligible probability).
A similar trick doesn't work with the scheme you propose since the verifier can query $$H(e)$$ before step 2, making reprogramming harder. The verifier can also influence the distribution of $$e'$$, for example by querying the oracle on many points and rejection sampling. If the simulator could somehow guess the challenge $$e$$, it could generate a transcript for a uniformly random challenge $$e'$$ and reprogram the oracle as $$H(e)=e'$$. But the probability of making the right guess is exponential in the size of $$e$$ and even if we were to make this size logarithmic and use rewinding, we run into issues. The verifier could compute the full table for $$H(e')$$ since there are only polynomially many possible values, making reprogramming impossible.
• Thanks a lot! Quick question, if the whole issue is that the verifier can query Hash(e) multiple times and affect the distribution, does it mean that setting $e'= Hash(e, a, y)$ would fix it? May 4 at 21:11
• At first glance, providing additional inputs to $H$ seems to prevent the problems I've outlined. May 8 at 20:48