tag:blogger.com,1999:blog-3722233.post115463587394561234..comments2020-05-31T01:14:25.681-04:00Comments on Computational Complexity: Zero-Knowledge SudokuLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-77754897691043084062012-11-14T22:27:23.667-05:002012-11-14T22:27:23.667-05:00I was thinking the same thing as the above poster ...I was thinking the same thing as the above poster until I read your reply here. The grid changes everything. Thanks for clearing that up so neatly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87597866639834802502009-05-27T15:24:07.625-04:002009-05-27T15:24:07.625-04:00When one says Sudoku is NP-complete, one should ke...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.<br /><br />http://11011110.livejournal.com/23221.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48296025639704576532009-05-27T15:19:10.391-04:002009-05-27T15:19:10.391-04:00What is confusing about this "proof" is there is a...What is confusing about this "proof" is there is an implicit trusted third party. Let's call him Charlie.<br /><br />After solving the Sudoku puzzle, Paula needs to give Charlie her solution, ... *and* a permutation.<br /><br />Victor gets to ask *one* of 28 possible questions, and Charlie gives him the (permuted) response.<br /><br />When Victor wishes to ask another question, Charlie first gets another (random) permutation from Paula, and then discloses the next (differently permuted) response.<br /><br />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.<br /><br />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?"<br /><br />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.<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64349454754518186102008-10-18T18:31:00.000-04:002008-10-18T18:31:00.000-04:00Sudoku is an NP problem because of the reduction t...Sudoku is an NP problem because of the reduction to graph coloring.<BR/>Imagine constructing a map where each region is an entry in the puzzle and each region is connected to each region in its row and each region in its column and each of the regions inside its 3 by 3 block. <BR/>Now, if we have 9 colors (where each color is a number) we have to now color that region such that each region its connected to (which is each region in its row, column and block) has to have a different color from it (or rather a different number). <BR/>The actual reduction would have to show that if we could solve any sized sudoku in sub np that we could solve map coloring in sub np, which would offer up a contradiction. Therefore, we now need to show that we can construct a sudoku puzzle that upon solving it, could give us an answer to any map coloring problem. <BR/>I would imagine that this would involve many partially completed sudoku puzzles in order to solve.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48070666699358487502008-08-27T14:31:00.000-04:002008-08-27T14:31:00.000-04:00I do not understand why sudoku would be NP.I do not understand why sudoku would be NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-162078022339664002008-08-23T21:06:00.000-04:002008-08-23T21:06:00.000-04:00you likely to get a lot more traffic after the sci...you likely to get a lot more traffic after the sciam plug. I wonder, since Paula is the one making the lockboxes, how prohibitive would it be to construct those boxes so that she could have 9 different keys for each lock, with each key producing a specific desired number? obviously there would need to be at least 81 such locks for this to work, and practically if the number of such locks were small enough, Victor could reject anything that seemed suspicious. I'm sure the presence of such manipulable locks depends on the algorithm used, but it seems like with only 3 bits of information in each box that it would be feasible for a lot of algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154779948747910882006-08-05T08:12:00.000-04:002006-08-05T08:12:00.000-04:00The paper on Zero Knowledge for Sudoku (with Ronen...The paper on Zero Knowledge for Sudoku (with Ronen Gradwohl and Benny Pinkas) that Lance refereed to is available here:<BR/>http://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku_abs.html<BR/><BR/>It contains both cryptographic and "physical" protocols.<BR/><BR/>Moni<BR/><BR/>PS It is hard to imagine that a person who has no interest in privacy would be interested in this sort of stuff...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154749835875575892006-08-04T23:50:00.000-04:002006-08-04T23:50:00.000-04:00Yes, I'm sure that would increase their belief in ...Yes, I'm sure that would increase their belief in the practical appeal of computer science: By my calculations, it would only take about 12 hours for Paula to convince Victor that she has a solution.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154747351315041852006-08-04T23:09:00.000-04:002006-08-04T23:09:00.000-04:00Cool post! There have often been discussions on th...Cool post! There have often been discussions on this weblog as to how we can increase the appeal of theoretical computer science, and explain to non-theorists what it is we do. Examples such as these, which will appeal even to a layperson, are perfect for that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154744083486629192006-08-04T22:14:00.000-04:002006-08-04T22:14:00.000-04:00Bram: Not so! That would let you find out that va...Bram: Not so! That would let you find out that various pairs of blank squares contain the same number, even if it doesn't tell you what number it is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154737880858722142006-08-04T20:31:00.000-04:002006-08-04T20:31:00.000-04:00By 'square' in that last comment, I meant 3x3 grou...By 'square' in that last comment, I meant 3x3 group, by the way.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154737839931043722006-08-04T20:30:00.000-04:002006-08-04T20:30:00.000-04:00Thanks Aaron, I understand now.Although I think ef...Thanks Aaron, I understand now.<BR/><BR/>Although I think efficiency could be improved a bit. Since the rows and columns are permuted randomly, when Victor asks for a complete square he could instead ask for three complete squares, as long as no two of them share a row or column.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154715074295637482006-08-04T14:11:00.000-04:002006-08-04T14:11:00.000-04:00Each square has its own lockbox, rather than there...Each square has its own lockbox, rather than there being a single lockbox for each row, column, and 3x3 group. There is a grid of lockboxes, and the verifier can choose to look at any row or column of it. So if Paula doesn't have a solution, while she could put "123456789" in any one of the rows or columns, she can't put this in all of them (since the ability to do so would constitute a solution), and the verifier might pick the one that she was unable to fill correctly.Aaronhttps://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154714514162650472006-08-04T14:01:00.000-04:002006-08-04T14:01:00.000-04:00Naive question: What prevents Paula from really ch...Naive question: What prevents Paula from really cheating and just putting "123456789" in each lockbox and a similar trivial permutation of the original puzzle? What step am I missing?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154658508543197002006-08-03T22:28:00.000-04:002006-08-03T22:28:00.000-04:00Bram: the third option (Of seeing a permutation of...Bram: the third option (Of seeing a permutation of the original puzzle) serves the purpose of letting the verifier verify that the puzzle is the same. He can see that the prover has indeed presented him with a permutation of the original puzzle, and since he could have checked any of the rows, columns, or squares, can be reasonably confident that the permuted puzzle has a solution. And of course, if the permuted puzzle has a solution, so does the original one. <BR/><BR/>--AaronAaronhttps://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154653287742301732006-08-03T21:01:00.000-04:002006-08-03T21:01:00.000-04:00Doesn't Victor also have to have the option of hav...Doesn't Victor also have to have the option of having Paula reveal all of the 3's (on n's) in the original problem so he can verify that they all map to the same token? It seems that without that Paula could give any random sudoku solved position but not one which maps to the given problem and still not get busted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1154640045667819442006-08-03T17:20:00.000-04:002006-08-03T17:20:00.000-04:00Cute. Now how does she prove that the solution is ...Cute. Now how does she prove that the solution is unique?Anonymousnoreply@blogger.com