Score:1

Crypto

Real-world instantiation of NIZK protocol from Fiat-Shamir

Proliferate309

2/16/24, 11:16 AM

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?

118

1 + 0

zero-knowledge-proofs

fiat-shamir

non-interactiveness

Score:0

Crypto

baro77

2/16/24, 3:06 PM

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)

+ 11

Proliferate309

2/17/24, 1:48 PM

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.

Lev

2/18/24, 4:44 AM

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.

baro77

2/19/24, 1:59 PM

@Proliferate309 I have just edited my answer to get the space to answer your comment

baro77

2/19/24, 4:33 PM

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

Proliferate309

2/20/24, 10:41 AM

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)?

Proliferate309

2/20/24, 3:08 PM

and if the ROM proof can't be adapted to this real-world instantiation then what's the point in having the ROM proof - what value does it add?

baro77

2/23/24, 10:21 AM

What I'm not getting in your POV is why you accept that an uniform/random enough hash is ok for security/soundness of "normal" proof, but you think it's not enough for ZKness... I mean if it's ok for the former imho it should be ok for the latter too, if I'm correct about the fact that the perfect randomness is what a real hash miss in comparison with an ideal RO (of course taking for granted you are ok for ZKness in ROM)

Lev

2/24/24, 2:52 AM

I can understand your concern @Proliferate309. I think programmable random oracles are very peculiar and non-intuitive.

Proliferate309

2/24/24, 9:12 AM

@baro77 Because for a 'normal' proof the only property of the ROM you need is the true randomnes. So if you replace the ROM with a real hash function that is prety close to random the ROM proof gives a good justification that the real hash function is also secure (although it doesn't actually say anything about the real hash function). But for a zk proof via Fiat-Shamir this isn't enough - you also need the fact that the Simulator can ensure the challenge is the hash of the commitment. It does this by choosing the output of the ROM - this is something which simply cannot be made to (continued)

Proliferate309

2/24/24, 9:13 AM

happen with a real hash function, hence why imo the proof of the zk-ness for ROM says absolutely nothing about the zk-ness of the protocol when you try to implement it in real-life, and which is why I'm questioning the purpose of such a proof.

baro77

2/24/24, 9:59 AM

thanks, now I get that your concern is about programmability and not about randomness. I know it's an open problem (e.g. Matthew Green is tweeting about it during last days - BTW are you the one he was asked by?); imho one side to explore is that Simulators seem not necessarily required to exist in real world, they are just required to exist out of protocol rules; more, I want to stress that any NI-ZK proof with "real world" simulator would be deniable (and so useless): from that POV the fact that Simulator doesn't exist "in real world" seems a feature.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Real-world instantiation of NIZK protocol from Fiat-Shamir

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.