3
$\begingroup$

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:

Interactive version of Schnorr's protocol How the simulator generates the output backwards

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$".

Program the hash function

And page 23 of the following lecture notes shows that the simulator can set $H$ to any arbitrary hash function.

Why does S have this ability to change the 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

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to realizing that the random oracle model is kinda weird. $\endgroup$
    – Maeher
    Dec 6, 2021 at 8:27
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2021 at 19:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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