Comment by ColinWright

Comment by ColinWright 4 days ago

7 replies

View on Hacker News

I can certainly explain it more, a question of "better" is debatable!

Here's the process:

(A) You give me a graph to 3-colour;

(B) I claim I can 3-colour it;

(C) You demand that I prove it;

(D) I colour it with colours ABC and cover the vertices;

(E) You point at an edge;

(F) I reveal the colours of the vertices at the ends of the edge;

(G) If I have coloured the graph then the colours revealed will always be different;

(H) We repeat this process with a permutation of the colours between each trial;

(I) If I'm lying then eventually you'll pick an edge where either the vertices are not coloured, or the have the same colour.

(J) This process reveals nothing about the colouring, but proves (to some level of confidence) that I'm telling the truth.

So ... what's unclear?

Instructions on how to email me are in my profile if you prefer ...

mathgradthrow 2 days ago

Ah, I see. This is not an example of a ZKP, because you are relying on a third party who has full knowledge of the coloring, which is wherever you have drawn your coloring.

Reply View 1 reply
  • ColinWright a day ago

    No, that is not the case. The process does not rely on a third party.

    Person A provides person B with the graph.

    Person B claims to have coloured it.

    Person A demands that they prove it.

    Person B hides the colouring

    Repeatedly:

    * Person A points at an edge

    * Person B reveals that the endpoints are differently coloured

    * Person B re-hides the colouring and permutes the colours

    If person B does not have a colouring, with probability 1 this process will fail and person A will know that person B does not have a colouring.

    But if person B does have a colouring then each step will succeed, and by repeating the process person A can achieve any desired degree of confidence that person B must, indeed, have a colouring.

    This process can be made digital rather than physical, and no third party need be involved. As a sketch of one step:

    * Person B colours the graph

    * For each vertex, person B generates a long random string, pre-pends the colour, applies a cryptographically strong hash function to that, and sends the result to A. This "Fixes and hides" the colouring

    * Person A asked for two "colours" to be revealed

    * Person B provide the associated "colour and random string"s, the pre-images of the requested hashes

    * Person A checks the hashes and now knows the colours of those two vertices.

    Should I write this up "properly"? It's already discussed elsewhere on the 'net.

    Reply View 0 replies
kadoban 4 days ago

How do I know/prove that you're not just saying any random two colors for whichever edge I choose?

Reply View 4 replies
  • ColinWright 4 days ago

    The version I'm describing has it physically sitting in front of you at the time, so you can see that the colours haven't been changed "on the fly" after you pick an edge. In this version:

    (A) I colour it;

    (B) I cover the vertices so you can't see any of them, but I can no longer change them;

    (C) You choose the edge, and I reveal the endpoints.

    Converting this to a digital version requires further work ... my intent here was to explain the underlying idea that I can prove (to some degree of confidence) that I have a colouring without revealing anything about it.

    So just off the top of my head, for example, I can, for each vertex, create a completely random string that starts with "R", "G", or "B" depending on the colour of the vertex. Then I hash each of those, and send you all of them. You choose an edge and send me back the two hashes for the endpoints, and I provide the associated random strings so you can check that the hashes match.

    Reply View 3 replies
    • lordnacho 4 days ago

      This reminds me of the "Where's Waldo (Wally in UK)" example:

      You can prove that you found Wally with a large piece of paper with a hole in it. You move the hole over Wally, and the person you're sitting with can see you found it, but he's no wiser about where.

      Reply View 2 replies
      • FridgeSeal 4 days ago

        Another way is to get them to put marks/signatures over the back of the blank. Overlay to e blank, and cut Wally out of it where he occurs on the actual page and give them the cutout.

        Reply View 0 replies