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
If you're looking for something at the level of paint cans, I think you want Matthew Green's "crayons and hats":

https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

>>tptace+Tg
That's only for interactive proofs though. Like GP I have no problem understanding those.

>>remram+Cz
There is a trick to convert an IP to a non-IP.

Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability.

So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc.

Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes.

The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.

>>_alter+rD
It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?