New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Peggy can get away with false solution #1

Closed
dooglius opened this Issue Aug 11, 2016 · 3 comments

Comments

Projects
None yet
2 participants
@dooglius

dooglius commented Aug 11, 2016

(x-posted from my comment on Hacker News)

Suppose that in a puzzle there is only one 1 and one 9 that do not overlap in any way (row, column, or 3x3 square). Now, suppose that Peggy comes up with a false solution to the problem which sets both of these tiles to 9. Then, neither the 1 nor the 9 can be picked for the green squares, and so no test of Victor's can disprove Peggy's false solution.

This seems easily fixable too: rather than the whole green tiles thing, just allow Victor to query either a row/column/3x3 to prove the solution is a valid sudoku, or query the original filled in tiles, to show that the solution corresponds to the original problem.

I've come up with an example (look at the 1 and the 9) and verified this:
screencapture-manishearth-github-io-sudoku-zkp-zkp-html-1470926941066

@Manishearth

This comment has been minimized.

Owner

Manishearth commented Aug 11, 2016

Good observation! I initially was going to go with having a preset option, but I didn't think it was necessary. Added. Will update post shortly.

@Manishearth Manishearth reopened this Aug 11, 2016

@Manishearth

This comment has been minimized.

Owner

Manishearth commented Aug 11, 2016

Wait, that solution is totally wrong. Hold on.

@Manishearth

This comment has been minimized.

Owner

Manishearth commented Aug 11, 2016

Should be fixed now 😄

Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment