4 ms·

My understanding is that there is a difference between the concept of a Zero-Knowledge Proof (ZKP), and then the applications that such a thing is possible. In

My understanding is that there is a difference between the concept of a Zero-Knowledge Proof (ZKP), and then the applications that such a thing is possible. In the example given, I can prove that N is composite without revealing anything (well, almost anything) about the factors. But in practice we want to use a ZKP to show that I have specific knowledge without revealing the knowledge itself. For example: You can give me a graph, and I can claim that I can three-colour it. You may doubt this, but there is a process by which I can ... to any desired level of confidence ... demonstrate that I have a colouring, without revealing what the colouring is. I colour the vertices RGB, map those colours randomly to ABC, and cover all the vertices. You choose any edge, and I reveal the "colours" (from ABC) of the endpoints. If I really can colour the graph then I will always be able to reveal two different colours. If I can't colour the graph then as we do this more and more, eventually I will fail. So you are right, but the message of the post is, I think, still useful and relevant.

mathgradthrow 11mo ago
can you explain this a little better?
- ColinWright 11mo ago
  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 ...
  - kadoban 11mo ago
    How do I know/prove that you're not just saying any random two colors for whichever edge I choose?
    - ColinWright 11mo 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.
      - lordnacho 11mo 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.
        fragmede 11mo ago
        https://youtu.be/5qzNe1hk0oY https://youtu.be/5qzNe1hk0oY for a video if you can't picture that.
        FridgeSeal 11mo 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.
- fragmede 11mo ago
  The key insight is that Colin can show you a red-green-blue coloring of the graph, and flip the whole graph secretly, so it's blue-red-green instead when you look at an individual section, but really the graph is yellow-pink-orange colored. Even after showing you all the intersections of the graph individually in the red green blue coloring to satisfy that he can 3-color it, you still have no idea what is yellow pink or orange on his copy of the graph.
hansvm 11mo ago
Suppose the graph admits only 4+ colorings, but when attempting a 3-coloring it's possible for only one edge to be misaligned. Then (A) you need O(n_edges) calls to the oracle to gain any confidence about the 3-colorability of a 3-colorable graph (else you might be easily duped by the one misaligned edge), and (B) in so doing, you learn almost all of the structure of the graph (since you have way more random calls than there are edges). Restating, not only is the ZK algorithm slow, but by the time you have confidence in the ZK proof you also have additional knowledge about the structure whose properties you're proving.
- ColinWright 11mo ago
  In the version I'm discussing, both parties already know the graph, so your point (B) seems irrelevant. The interrogator needs to know the graph in order to specify an edge (and to know that they've done so), so I'm not sure of the precise version you are thinking of. Put point (A) is relevant ... certainly each call only provides a small amount of additional confidence, so a lot of calls might be required. Even so, the system seems sound to me, and I'd appreciate any details of ways in which it is not. See also my comment here: https://news.ycombinator.com/item?id=46121137 https://news.ycombinator.com/item?id=46121137 That gives more detail of the setup, and how it can be implemented digitally.

mathgradthrow 11mo ago

can you explain this a little better?

ColinWright 11mo ago
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 ...
- kadoban 11mo ago
  How do I know/prove that you're not just saying any random two colors for whichever edge I choose?
  - ColinWright 11mo 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.
    - lordnacho 11mo 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.
      - fragmede 11mo ago
        https://youtu.be/5qzNe1hk0oY https://youtu.be/5qzNe1hk0oY for a video if you can't picture that.
      - FridgeSeal 11mo 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.
fragmede 11mo ago
The key insight is that Colin can show you a red-green-blue coloring of the graph, and flip the whole graph secretly, so it's blue-red-green instead when you look at an individual section, but really the graph is yellow-pink-orange colored. Even after showing you all the intersections of the graph individually in the red green blue coloring to satisfy that he can 3-color it, you still have no idea what is yellow pink or orange on his copy of the graph.

hansvm 11mo ago

Suppose the graph admits only 4+ colorings, but when attempting a 3-coloring it's possible for only one edge to be misaligned. Then (A) you need O(n_edges) calls to the oracle to gain any confidence about the 3-colorability of a 3-colorable graph (else you might be easily duped by the one misaligned edge), and (B) in so doing, you learn almost all of the structure of the graph (since you have way more random calls than there are edges). Restating, not only is the ZK algorithm slow, but by the time you have confidence in the ZK proof you also have additional knowledge about the structure whose properties you're proving.

ColinWright 11mo ago
In the version I'm discussing, both parties already know the graph, so your point (B) seems irrelevant. The interrogator needs to know the graph in order to specify an edge (and to know that they've done so), so I'm not sure of the precise version you are thinking of. Put point (A) is relevant ... certainly each call only provides a small amount of additional confidence, so a lot of calls might be required. Even so, the system seems sound to me, and I'd appreciate any details of ways in which it is not. See also my comment here: https://news.ycombinator.com/item?id=46121137 https://news.ycombinator.com/item?id=46121137 That gives more detail of the setup, and how it can be implemented digitally.