I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics.

I understand the interactive steps are:

1. P wants to proof he knows x where y = g^x
2. P picks a random v and computes t = g^v and sends t to V
3. V picks a random c and sends it to P
4. P computes r = v - cx and sends it to V
5. V checks t = g^r * y^c

while the non-interactive steps would be like this:

1. P wants to proof he knows x where y = g^x
2. P picks a random v and computes t = g^v and keeps it as first term of the proof
3. P computes c = H(g,y,t)
4. P computes r = v - cx and keeps it as second term of the proof
5. V checks t = g^r * y^H(g,y,t)

Now I see V doesn't actually get any hint about the value of x P wants to proof he knows whithout revealing.

But the definition for Zero-Knowledge should be a Simulator could compute the whole proof in probabilistic polynomial time.

How can this definition be applied to the non-interactive procedure? How can a simulator repoduce the proof (calculating the correct hashes) if he does not know x, thus he can't compute r which is part of t which in turn is an input of H?

Can anybody link me some simple explanation of this?


Going ahead in my research, and fallowing some hint form the useful comments I could produce some further consideration:

  1. Such non-interactive protocol is honest verifier since the verifier doesn't really have any strategy he can fallow but simply checking the provided demonstration holds.
  2. As suggested by @xagawa and this link the simulator has complete freedom on what he can do to "come up" with the couples (t,r) he sees in the proof, so he can just pretend the oracle works according to his needs.

The linked paper states as fallows:

So, our simulator now works as follows. Recall the statement PK{(α) : A = g α}. (Remember that here the simulator does not know x such that A = g x !) Instead, the simulator chooses random values c, s ∈ Zq as before and computes T = g s/Ac . The simulator then “sets” H(T) = c.

According to this I figured out a simulator may see the generation of each (t,r) as the invocation of a random oracle H'(t) such that r = H'(t) observing that H'(t) is in fact a random oracle itself on the couples (t,r) since:

  1. Given a starting t, H(g,y,t) generates a truly random c and the output r = v - cx of H'(t) is directly bound to such a truly random value
  2. For a given input t, H(g,y,t) always generates the same output c which in turn produces the same r

This way the concept of simulation reduces to the invocation of a random oracle on a random input t to obtain r.

Does all this make sense? Is it correct or do I miss something crucial?


@Robert NACIRI comments seem to suggest that in fact the verifier challenges the prover by agreeing on a common random oracle H to use, so than the concept of zero-knowledge in this case may become something like this:

No matter what random oracle you agree to use, if a simulator can see all your output couples as input and output of another "wrapping" random oracle then the only proof of your knowledge lays in the agreement you had with the verifier to actually use the specific random oracle H and the proof is zero-knowledge.

Does this statement make sense? Please correct me if possible and link any better explanation if you know any.

Thanks again for the useful comments and help.

  • 1
    $\begingroup$ I think a step where V send a challenge could be missed. For alternative implementation of ZK, you can probably get inspired by the GQ protocol -> en.wikipedia.org/wiki/Zero-knowledge_proof Bye. $\endgroup$ – Robert NACIRI Feb 22 '15 at 21:21
  • 3
    $\begingroup$ Hint: Notice that the simulator can program the random oracle and the original protocol is honest-verifier ZK. $\endgroup$ – xagawa Feb 23 '15 at 13:23
  • 1
    $\begingroup$ To make Verifier capable of producing simulated session transcript, one would do an OR-proof: either Prover knows his secret $x$, or he knows Verier's secret (not mentioned in the problem statement). $\endgroup$ – Vadym Fedyukovych Feb 24 '15 at 12:37
  • $\begingroup$ @Robert NACIRI - this is non-interactive Zero Knowledge Proof, there's no sending of a challenge from V $\endgroup$ – Onheiron Feb 28 '15 at 14:42
  • 1
    $\begingroup$ @Onheiron, I understand, but my question is simple. How the Verifier get (r,y,t)? by telepathie? This is why I said that something is missing. In my sense, in all the ZK protocols I know there is exchange of challenges between P and V. $\endgroup$ – Robert NACIRI Feb 28 '15 at 15:21

Your Answer

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

Browse other questions tagged or ask your own question.