We show a
pictorial demonstration of a zero-knowledge protocol for Sudoku
using playing cards. It corresponds to Protocol
3 in the paper.
The equipment
needed is a blank board with the Sudoku grid drawn on it
and several standard decks of cards with identical patterns on
their back. Each card represents a value in the range 1-9 (the
precise assignment is not important). The two participants are called prover and verifier.
They both know a Sudoku puzzle and the prover knows (or so he claims) a
solution to it. The prover
wants to convince the verifier
that he knows
the solution without giving information about it.
The
protocol:
A demonstration of the Protocol
The equipment needed: several standard decks of playing
cards
with the same background, and a 9 x 9 board.
The puzzle:
Step 1: The verifier
(or the prover) places
the cards
according to the Sudoku puzzle.
Three card faced up on filled-in cells.
Step 1: The prover
places cards on the remaining cells following his solution.
Three identical valued cards on each cell face down.
Step 1: The entire board at the end of the step.
Step 2: The verifier
starts making packets, one for each
column.
From each cell in each column one of the three cards is chosen at
random.
Step 2: A closer look.
Step 2: Similarly, the verifier makes packets for the rows:
Step 2: Finally, the verifier makes packets for the sub-grids; end of the step.
Step 3: The prover turns over the cards faced up in each packet and shuffles them.
Step 4: The verifier opens the packets and sorts to see that all 9 values appear in every packet.
This site made with child labor.