Zero knowledge / proof of knowledge sudoku solution

Question

I recently started a coursera course "cryptography 1" provided by Stanford university. In one point when explaining zero proof knowledge the instructor mentions the following:

Almost any puzzle that you want to prove you have an answer to, you can prove it is your knowledge. For example let's say that you have a sudoku puzzle which you wanna prove you know the solution to, you can prove it to Bob In a way that Bob would learn nothing at all about the solution but he would still be conviced that you know the solution to it.

I am terribly confused by this. How would one prove that he can solve a sudoku puzzle and prove it to X (in this case Bob) without transmitting the actual solution?

Answer 1

Rough scetch, assuming Bob is standing next to you in the same room:

• Prepare cards with the correct numbers on them
• Lay down the cards according to the setup, face up
• Lay down the remaining cards with the correct solution, face down, so that Bob can't see them.

Now you let Bob choose one column, row or sector.

• You pick up the cards in that row, column or sector, still not showing them to Bob (turn around face-up cards if there are any), and start shuffling them.
• Hand them to Bob, who can see if the cards have the correct numbers (1-9 in the standard game).

After shuffling, Bob can't see any more which card was in which position, he just knows that the set of cards is the correct one. If the face down solution is correct, this will always work out correctly. If you don't know the actual solution, there is a nonnegligible probability to be caught cheating. The chance for catching cheating is quite low tho, so you need to do many repetitions of this to achieve an overall acceptable probability.

All of the processes can be done cryptographically, e.g. face down cards can realized by commitments, shuffling is known from MPC, mix nets, etc.

Edit: Alternative solution from this blog: Apply a permutation to the numbers, then you don't need shuffling. However, then you need to prove that the solution actually fits the setup of fixed numbers under that permutation. Therefore, Victor can also choose to see the permuted original puzzle.