Hacker News Reader

Comment by GotAnyMegadeth | Hacker News Reader

In his example Google could colour each vertex a completely different colour. That way when you revealed any random two it would always look like that had done it correctly. I suppose to get round this you have Google tell you which three colours they are using in advance.

View on HN

That wasn't spelled out perfectly in the post. The answer is that the set of crayon colors (e.g., red, blue, purple) is fixed and known to all parties. The only thing Google gets to swap is the ordering of which of the three colors it uses to color in each vertex. If I pull off a hat and find an illegal color -- e.g., hot pink, no color at all -- then I know Google is cheating.

This is a good time to point out that the solution to GOOG rainbow color cheating isn't to reveal 4 instead of 2 and make sure only 3 colors are seen, because then GOOG wouldn't have to get paid because you'd end up with a long enough list of known pairs to not need their services, because each trial run would leak exactly one pair (assuming a trial didn't indicate GOOG cheating, obviously). This is also why GOOG has to shuffle between each and every sample.

Its interesting to think about acceptable losses in zero knowledge... If the GOOG had the computing power to solve a problem 1000x bigger than you can solve, they can leak down to only maybe 10x and it'll still economically make sense for you to play fair and pay them.

Another fun mental exercise is to analyze the info leakage rate and truth belief rate of allowing GOOG to falsify 1%, 1/3, 1/2 of all colors.

Actually, it's not necessary to build a list of known pairs that you eventually link into a solution; if a challenge reveals at least three vertices you can identify each vertex unambiguously one by one. (That's because there are only three colors, so as long as you include the same two vertices v1, v2 in every challenge, you can classify every vertex into [color of v1], [color of v2], or [color 3] as soon as you see it.) A list of pairs only becomes necessary when there are more than three colors allowed.

This is explicit in the OP:

> Google can now enter enter[sic], shuffle a collection of three crayons to pick a random assignment of the three agreed-upon crayon colors (red/blue/purple, as in the example above), and color in the graph in with their solution.

Reply on news.ycombinator.com