zlacker

>>doomro+(OP)
Anyone have a good explanation on the intuition of non-interactive zero-knowledge proofs? For example, I thought the "paint-mixing" analogy for Diffie-Hellman key exchange (https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Ge...) really helped me handwave the math into "mixing easy, unmixing hard".

https://blog.cryptographyengineering.com/2014/11/27/zero-kno... was a good intro for interactive ZK proofs but I haven't been able to find something for non-interactive ones.

This blog post comparing ZK-STARKs to erasure coding is in the right flavor but didn't quite stick to my brain either: https://vitalik.eth.limo/general/2017/11/09/starks_part_1.ht...

>>bobbie+yc
"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof.

>>supern+Kd
This is an interactive example, isn't it? It doesn't help me understand non-interactive proofs like SNARKs/STARKs, where the verifier isn't communicating live with the prover.

>>bobbie+Ne
Look for the "Fiat Shamir heuristic" to understand the non interactive part.

It basically consists in the prover getting its random challenges from hashing public inputs, rather than from the verifier's coin tosses.

>>quantu+Sl
Thank you!!

If I understand correctly:

* The prover commits to a starting value (public input)

* Instead of waiting for an interactive challenge, they hash it and use the resulting hash output as if it were a challenge

If we believe the hash is a random oracle (as we do for cryptographic hash functions), then it is hard for the prover to manipulate the challenges. Is that it?