1
$\begingroup$

So I understand how one can use Fiat-Shamir to turn a HVZK sigma protocol into a non-interactive zk protocol in the random oracle model. My problem though is I don't understand why is this useful.

If I wanted to use a NIZK in something and I choose a protocol based on Fiat-Shamir, this would mean I have to choose a hash function which surely invalidates the zk proof in the ROM. So do I know anything about the zk-ness of this instantiated protocol I'm then using?

Normally for proofs using the ROM I believe the idea is that even though you have to choose a real hash function, if you make a good choice your hash function simulates randomness close enough that it shouldn't really matter to the proof of security and therefore you have some justification/belief that what you're using remains secure. But for NIZK this doesn't appear to be the case and the proof of zk fully breaks down if you have to choose a hash function.

If this is the case then why do people bother with creating NIZK schemes via Fiat-Shamir which have only been proved in ROM?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

But for NIZK this doesn't appear to be the case and the proof of zk fully breaks down if you have to choose a hash function

Why you say so?

The original HVZKP's Simulator is a good starting point for Fiat-Shamir NIZK's Simulator since the hash output is uniform enough. The added requirement is that RO must be programmable by the Simulator (maintaining the uniformity), to take into account the fact that simulators often play with stuff out of order. ROs (and hashes) commit their output to the input, so they aren't programmable, they enforce a temporal order of messages; but remember that Simulators don't play with the rule of the protocol, they can produce fake transcripts acting out of protocol rules, and Random Oracle/Hash programmability is one of their "superpowers"

So, IMHO, passing from theoretic RO to actual Hash the only additional assumption for ZK is just enough uniformity of hash output.

EDIT TO ANSWER OP's FOLLOW-UP COMMENT

Fiat-Shamir prescribes the Random Oracle used by the prover and by the verifier is the same. Simulator is an entity playing out of protocol rules, but verifier has to follow them. So in Fiat-Shamir when the simulator is progamming the random oracle, it programs it for both the prover and verifier. Imagining the verifier using "original" oracle instead of the simulator-programmed-one puts him out of protocol, so it's out of our boundaries.

Using Hashes to simulate RO means prover and verifier have their own implementations of the prescribed hash, but it doesn't mean they can use different ones (if they want to follow the protocol); the simulator has to programme both the prover's and verifier's hash implementations.

Of course this sounds very strange, but not so much if you take into account that sometimes rewinding capability of simulator in interactive proofs is represented as prover and verifier being VMs in a computer and the simulator being the VMs hypervisor, able to pause and repeat their runs manipulating their state: in that case simulator can pause and rewind time flow... a quite huge superpower I would say :)

Coming back to our verifier calling an hash... now the prover and the verifier are VM which never interact (a part from the prover leaving the proof somewhere for the verifier to read it), but they both call their functions implementing the hash. And now our "hypervisor" simulator can change how both those functions works... why this should be worst than pausing and rewinding time?

Your central point seems to be the fact a verifier using "original" hash (the one not programmed by the simulator) would recognize the simulator's fake transcript:

  • I have just said in that case the verifier wouldn't be following protocol rules cause it would use a RO/hash different from the one of entity pretending to be the prover;
  • more, that detection capability imho is fundamental in any non-interactives proofs (Fiat-Shamir based or not): otherwise NI-ZKPs would be deniable, making themselves useless (a NI prover could always pretend that a previously published proof is fake and produced by a simulator)
Improve this answer
$\endgroup$
11
  • $\begingroup$ Well a Simulator should simulate a real proof right? But if it chooses the hash function then with overwhelming probability it won't be the one chosen at the start of the protocol. And so it can't simulate a proof because it would be immediately obvious that it's using a different hash function to the one used in the protocol. Because from the transcript of the proof you can easily check if H(t,y) =/= H'(t,y) where H is the hash function I chose and H' is the hash function chosen by the Simulator. $\endgroup$
    – Proliferate309
    Feb 17 at 13:48
  • $\begingroup$ You are saying something very specific there by assuming that the hash function is chosen by the protocol. It could be baked into the protocol in which case the simulator does not need to choose anything. $\endgroup$
    – Lev
    Feb 18 at 4:44
  • $\begingroup$ @Proliferate309 I have just edited my answer to get the space to answer your comment $\endgroup$
    – baro77
    Feb 19 at 13:59
  • $\begingroup$ @Lev was your comment for me or for the Proliferate309 ? If It was for my initial answer, please let me know if my follow-up still miss your point! $\endgroup$
    – baro77
    Feb 19 at 16:33
  • $\begingroup$ Thanks for the update but it feels like you might be misunderstanding my question a bit. I get in the ROM the simulator can prescribe hash function for all parties. But I am talking about a real instantiation of a zk protocol and given ROM proof does tell us anything about the zk-ness of this instantiation? i.e. we know the protocol is zk under ROM but do we know anything about the zk-ness of the real protocol? My intuition/guess would be to try use ROM proof but adapt to real world. But how could we show a Simulator exists for the real-wrld version of the protocol (and therefore show zk)? $\endgroup$
    – Proliferate309
    Feb 20 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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