Zero-Knowledge Sudoku: Verifying solution without looking at it. | Hacker News Reader

Zero-Knowledge Sudoku: Verifying solution without looking at it.

blog.computationalcomplexity.org

32 pointsamichail11 comments

What is confusing about this "proof" is there is an implicit trusted third party. Let's call him Charlie.

After solving the Sudoku puzzle, Paula needs to give Charlie her solution, ... and a permutation.

Victor gets to ask one of 28 possible questions, and Charlie gives him the (permuted) response.

When Victor wishes to ask another question, Charlie first gets another (random) permutation from Paula, and then discloses the next (differently permuted) response.

The confusion comes from some readers thinking Paula is the one telling Victor a row, column, block, etc., ... and thus perhaps she might lie or cheat.

Victor needs to be able to rely on the trusted referee who knows the solution, and all Paula is allowed to do is give (valid) permutations, ... and then Victor will be convinced. If Victor needs to rely on Paula, then Victor could save everyone a lot of work and simply ask Paula, "Have you solved this Sudoku puzzle?"

In fact, since Victor needs to be able to rely on a trustworthy third party, Victor need only ask Charlie: "Did Paula give you a valid solution?", ... again, saving everyone lots of work.

While article does talk about Victor being convinced of something (Paula solved the puzzle) with Zero-Knowledge of the specific details of the solution, ... it doesn't seem to be a useful example of how Zero-Knowledge proofs can be put to practical use in Computer Science applications.

I don't think you're correct, although I upvoted you before I thought that because you seemed to be explaining the problem I had with the article. However, reading the article's comments it becomes clear that there's 81 locked boxes, one for every cell in the Sudoku grid. The key Victor chooses from the 28 Paula proffers will open nine of the 81 boxes. Those nine have to be consistent amongst themselves, i.e. a permutation of 1-9, despite Paula not know which of the 28 keys would be chosen.

Charlie doesn't exist, nor does he need to.

I don't think this proof works, or maybe it embeds the assumption that "Paula is actually doing what she says she is doing" so far up that I can't see it.

If Victor chooses a row, I tell him "123456789". Victor accepts because each number appears once.

If Victor chooses a column, I tell him "123456789". Victor accepts because each number appears once.

If Victor asks to see my permutation, I return the actual problem. Victor accepts because that is a valid permutation of the actual problem.

Sure, I had to precompute the answer and put it in lock boxes, but since he only gets to see one lockbox per run I don't have to make the lockboxes internally consistent, do I? After all, I am a wicked woman trying to deceive Victor into thinking that I have solved his Sudoku puzzle.

(If you think Victor will eventually clue into me always choosing the same "random" permutation such that he gets 123456789 as the result, then you're giving Victor an awful lot of credit for what is essentially a math proof. Regardless, I can randomize any of my lockboxes by the same logic.)

"Sure, I had to precompute the answer and put it in lock boxes, but since he only gets to see one lockbox per run I don't have to make the lockboxes internally consistent, do I?"

Yes you do. The lockboxes must be filled before Victor makes his choice, you cannot change their contents afterwards. Therefore, you cannot return the actual problem when he chooses that and 12345678 when he chooses a row or column. That would require changing the boxes after his choice.

Also, if all rows contain 12345678 (same order), then columns contain 111111111, 222222222, ...., 999999999, not 12345678.

Ahh, I get it now:

the problem supposes there are 81 lock boxes and 28 keys. Each key opens the appropriate 9 lock boxes. Victor gets to pick one key and see the 9 appropriate boxes, after I have stuffed all the boxes.

I had thought there were 28 lock boxes and Victor gets to see one of them, after I have stuffed all the boxes.

a bit laborious for a probability based solution. was expecting some clever trick based on the headline.

The point of this is not to actually verify a Sudoku solution without looking at it.

Zero-knowledge proofs are one of the central concepts in computational complexity. Remember that this is an area of study where the fact that something exists often means much more than how to actually construct it. This post was an attempt to explain zero-knowledge in a slightly more fun way instead of the usual example that uses graph isomorphism.

Perhaps it is not the right topic for HN, but it is hardly 'laborious', given the context.

That you can do this at all might be surprising to people unfamiliar with zero-knowledge protocols.

"When one says Sudoku is NP-complete, one should keep in mind that this refers only to an unusual type of Sudoku puzzle in which there might be multiple solutions."

http://11011110.livejournal.com/23221.html

How can this be called "Zero-knowledge" proof?

Based on the information from the proof given by Paula, victor can solve the problem atleast partially, right? What am I missing here?

"Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question."

Reply on news.ycombinator.com