3 ms·
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 yo
by mathgradthrow 10mo 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.
- ColinWright 10mo agoNo, 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.
- mathgradthrow 10mo agoOk, I still contend that this is not a ZKP without the hashing scheme, but I agree that with the hashing scheme, it is.