Fiat-Shamir with interactions

pintor

4/28/24, 3:04 PM

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:

The prover $\mathcal{P}$ compute $a$ exactly like in $\Sigma$-protocol and sends it to the verifier $\mathcal{V}$.
The verifier $\mathcal{V}$ replies with a challenge $e$. So far, everything is like in $\Sigma$-protocol.
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?

1 + 2

zero-knowledge-proofs

fiat-shamir

random-oracle-model

lamontap

5/1/24, 8:59 PM

So your goal is taking a $\Sigma$-protocol that is only known to be HVZK and making it ZK?

pintor

5/3/24, 7:16 AM

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

Score:1

Crypto

lamontap

5/3/24, 8:34 PM

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.

But as you hinted in your question, this scheme does not seem all that useful, especially in a model (the ROM) where you can make the whole thing non-interactive.

+ 2

pintor

5/4/24, 9:11 PM

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?

lamontap

5/8/24, 8:48 PM

At first glance, providing additional inputs to $H$ seems to prevent the problems I've outlined.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Fiat-Shamir with interactions

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.