Skip to main content
Cryptography

Return to Question

some further consideration based on comments
Source Link
Carlo Moretti
Carlo Moretti
  • 111
  • 4

EDIT

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?

EDIT 2

@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.

Thanks

EDIT

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?

EDIT 2

@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.

edited tags
Link
Carlo Moretti
Carlo Moretti
  • 111
  • 4
Source Link
Carlo Moretti
Carlo Moretti
  • 111
  • 4

Zero Knowledge Non Interactive Proof with random oracle

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?

Thanks