3 ms·

I didn't quite follow how you can actually prove that you've solved a sudoku via reduction to graph coloring. If I understand correctly, an important part of th

I didn't quite follow how you can actually prove that you've solved a sudoku via reduction to graph coloring. If I understand correctly, an important part of the graph coloring protocol is that the prover permutes the colors between each round (otherwise the verifier can just iteratively learn the color of every node). But all sudoku puzzles have the same graph structure - a puzzle instance is a partial assignment of colors to nodes. So can't a verifier can gain knowledge about the prover's solution by asking for edges that correspond to known values? (I found a different ZKP protocol for sudoku, but I don't think it relates to the graph coloring protocol: https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/ https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/)

tdb7893 2y ago
I haven't read this particular blog but the solution I remember seeing is you randomly swap the colors each edge verification so each is independent. All the edges are numbers that are required to be different so when you verify they are different you gain no information.
- jkaptur 2y ago
  How does the verifier gain confidence that the prover has solved a particular instance of a sudoku puzzle?
  - heinrich5991 2y ago
    They can ask whether the pre-filled fields have the correct equal/unequal relationship by testing two of them at a time.
benediktwerner 2y ago
The way the conversion is done here, different sudokus produce different graphs. Besides the regular sudoku graph structure, there are nine additional nodes, each corresponding to one number. They are all connected to each other to ensure they must be different and each one is connected to each cell where the corresponding number is present as a clue from the start. This way, the graph doesn't need any pre-coloring to still encode the sudoku including the given clues.
- jkaptur 2y ago
  Ah ha! Thank you for explaining.

tdb7893 2y ago

I haven't read this particular blog but the solution I remember seeing is you randomly swap the colors each edge verification so each is independent. All the edges are numbers that are required to be different so when you verify they are different you gain no information.

jkaptur 2y ago
How does the verifier gain confidence that the prover has solved a particular instance of a sudoku puzzle?
- heinrich5991 2y ago
  They can ask whether the pre-filled fields have the correct equal/unequal relationship by testing two of them at a time.

benediktwerner 2y ago

The way the conversion is done here, different sudokus produce different graphs. Besides the regular sudoku graph structure, there are nine additional nodes, each corresponding to one number. They are all connected to each other to ensure they must be different and each one is connected to each cell where the corresponding number is present as a clue from the start. This way, the graph doesn't need any pre-coloring to still encode the sudoku including the given clues.

jkaptur 2y ago
Ah ha! Thank you for explaining.