2
$\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?

Edit: To add more details of my issue with the ROM for NIZK protocols - when constructing a simulation of the transcript, the simulator has control of the output of the random oracle. This can never be achieved using a real (sufficiently good) hash-function so simulated transcripts cannot be shown to exist using a similar argument to the ROM proof. Therefore nothing about the ZK-ness of the protocol using a concrete has function is known.

$\endgroup$
9
  • $\begingroup$ There seems to be a misconception on proofs in the ROM. All proofs in the ROM are basically heuristic. They don't guarantee anything upon the choice of a concrete hash function. This is basically how to know, there could not exist a hash function that implements a random oracle. Now, for concrete hash, we can get certain confidence that it behaves like a random oracle. So, it doesn't matter whether it's HVZK or other scheme, proofs in the ROM do not really carry over when we fix a concrete hash. $\endgroup$ Nov 16, 2023 at 15:18
  • $\begingroup$ @MarcIlunga I mean that is exactly what I was saying but I don't agree with the sentence "Now, for concrete hash, we can get certain confidence that it behaves like a random oracle" for proofs of NIZK in the ROM. Precisely because to me it seems like the entire proof breaks down once you have to choose a hash function unlike other ROM proofs where a good enough hash function should behave similarly to a ROM. In a NIZK ROM proof you need more than just "a good enough hash function should behave similarly to a ROM" which I why I query the usefulness of such proofs entirely. $\endgroup$ Nov 20, 2023 at 11:55
  • $\begingroup$ Can you explain what you mean by the proof breaks down? The point I am maling is that the proof always beaks down even for other ROM proofs. e.g.: There exists signatures schemes secure in the rom but insecure for any choice of hash function, even good enough ones. AFAIK, the situation is similar with Fiat Shamir. In the sense that, v theses counter examples are somewhat contrived but nevertheless valid counter Examples to the "soundness" of the ROM $\endgroup$ Nov 20, 2023 at 12:32
  • $\begingroup$ What is quite concerning with the F-S at the moment is non interactive recursive proofs. Which seemgling runs directly into issues of trying to simulate a random oracle with finte resources. $\endgroup$ Nov 20, 2023 at 12:44
  • $\begingroup$ @MarcIlunga You make a good point. Instead of answering your question I'd instead like to ask another one - since there exists these schemes which are secure in ROM but insecure for any choice of hash function, what is the purpose of a proof in ROM? I see many NIZK protocols which only give security proofs in the ROM - it seems to me that this adds no value as it adds no assurance to the security of the protocol since as you say there are counterexamples. So why do people bother with proofs in ROM at all? $\endgroup$ Nov 20, 2023 at 14:44

1 Answer 1

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)
$\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$ Feb 17, 2023 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, 2023 at 4:44
  • $\begingroup$ @Proliferate309 I have just edited my answer to get the space to answer your comment $\endgroup$
    – baro77
    Feb 19, 2023 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, 2023 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$ Feb 20, 2023 at 10:41

Your Answer

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

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