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

Question

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

• https://crypto.stanford.edu/cs355/19sp/lec5.pdf
• What is a Non-Interactive Zero Knowledge Proof?
• How does the simulator of the special-honest verifier zero-knowledge property works?
• Is a hash a zero-knowledge proof?
• https://www.impan.pl/konferencje/bcc/2019/19-simons-x/zero_knowledge_primer_2.pdf

Answer 1

A key point here is that in Fiat-Shamir transformation, you need to make a distinction between what security means in real implementation and what it means in the theory of your design. It is true that in practice we use hash functions to implement Fiat-Shamir transformation, but as you mentioned it doesn't seem easy to simulate the proof in this case. In theory, however, we use an ideal object called "random oracle" and depending on which properties we assume for this random oracle, we can perform the simulation. More precisely, a random oracle can be either programmable or non-programmable. By programmability, it means that the simulator is allowed to choose the answers to the oracle queries. In the context of non-interactive zero-knowledge (NIZK) proofs, for example, this makes the simulator able to create a convincing but fake proof. On the other hand, the non-programmable random oracle (NPRO) model restricts the simulator such that it can no longer choose the answers for the queries. Instead, the simulator is only empowered by seeing all the query/answer pairs, made by the parties during the protocol. This restriction on the simulator (or more generally, the security reduction) makes the underlying proofs preferable, as they rely on fewer properties of the random oracle and so can be considered as a step toward getting rid of it. But, in some NIZK proofs such as Fiat-Shamir transformation of Schnorr's protocol, programming the random oracle seems crucial to provide ZK property.