# How does the simulator generate a correct transcript under HVZK with the Fiat-Shamir heuristic?

## Background

I understand the interactive version of Schnorr's protocol and I understand how the simulator can generate an output that is i.i.d to the output of the prover-verifier:

## Question

What I don't understand is how does the simulator generate a correct transcript when we move to the non-interactive version of the Schnorr identification protocol? Page 4 of the 2019 CS355 lecture notes shows that the simulator can "Program $$H(g,h,u)$$ to be $$c$$". And page 23 of the following lecture notes shows that the simulator can set $$H$$ to any arbitrary hash function. This seems weird to me and I don't get it. Why do we assume that S has the ability to choose any hash function? In reality there will be some fixed hash function that we use to generate the random challenge $$c$$, right?

My understanding is the HVZK proof doesn't work if we don't allow the simulator to make up any hash function. Assuming we have a fixed preimage-resistant hash function, the simulator cannot generate the prover's messages $$u$$, $$z$$ in a manner consistent with that challenge. In the interactive case, the simulator can choose $$z$$ and $$c$$ randomly and work backwards to get $$u$$ deterministically where $$u = \frac{g^z}{h^c}$$. But in the noninteractive case you need to find $$u$$ and $$c$$ such that $$u = \frac{g^z}{h^c}$$ AND $$H(g,h,u) = c$$, and this is NP-hard. So you lose the zero-knowledge property since a simulator cannot generate a valid transcript.

So how are non-interactive zero-knowledge proofs of knowledge implemented in practice?

## Bibliography

• Welcome to realizing that the random oracle model is kinda weird. Dec 6, 2021 at 8:27
• It seems this question doubts that one can get some expected hash output by picking some input at random, with reasonable success probability and number of tries, and still comply with secure hash definition. Maybe I would doubt that too, but let me encourage you to talk to your professor first. Dec 6, 2021 at 19:21