Zero-Knowledge Sudoku

Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol. Paula goes to a different room than Victor and chooses a random permutation σ of {

[smoking186]

ゼロ知識. コメント欄にNaor, Cohen, Aaronsonって大人気だな