← Back to context

Comment by tptacek

6 months ago

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...

7 comments

tptacek

Reply
remram  6 months ago

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

  • _alternator_  6 months ago

    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.

    • remram  6 months ago

      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?

      2 replies →