On: Zero Knowledge Proofs: An illustrated primer (2014...

[alistproducer2]

Question about the hat example given:

The author says that the phone company wouldn't learn anything about google's solution by keeping notes because of the randomization of the coloring. that doesn't seem to be true to me.

Assuming the solution that Google colored in was correct, the phone company doesn't necessarily need to know the frequencies of the edges, merely that they are different: which is learned by recording the results after E^2 selections.

Am I wrong here?

[Manishearth → alistproducer2]

These are always adjacent nodes being compared. Assuming the solution is correct, adjacent nodes will always have a different color.

So the most information that can leak is the correctness of the solution. Which is exactly what we need.