We use Fiat–Shamir heuristic to turn Schnorr ZK to NIZK. So now NIZK is secure against chosen message attacks in the random oracle model, that is, ideal hash function: every unique query leads to a truly random response.

Ok, I get why our Hash function should not be reversible - otherwise, we disclose skey.

But what is the danger of collisions?

Suppose, a prover computes NIZK proof (r,c):

c = Hash( g || V || pkey || User Id || Other Info )

r = v + skey*c mod q

V = g^v mod p, v - random

Even if I find any other combination that results in c, it's unlikely I can forge proof.


First, I do not think reversing the hash function will help you disclose skey as nothing in the Hash needs to be private. The Hash in Schnorr NIZK is a practical instantiation of the random oracle, not perfectly though. Here the random oracle is used to commit or sign V, so that you can not choose V based on c. Note that it is trivial to get V given y, c, g, r, and pass the verification $Vy^c = g^r$.

As for the danger of collisions, it may not be very relevant to the security proof. Hash functions are just how we implement random oracles in practice. I think a better way to look at this is as follows. If one can forge a proof, then c should be equal to the output of the random oracle with input (g, V, pkey, ...). This happens with small probability, as a random oracle always outputs a purely random value given a new input.

  • $\begingroup$ You are right, all values in the Hash are public - there is no danger for skey. $\endgroup$
    – pintor
    Jan 25 '18 at 9:32

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.