Using Standard Playing Cards

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:

- The prover places three cards on each cell. On filled-in cells of the puzzle he places three cards with the assigned value, faced up (this can be done by the verifier as well). On the rest of the cells the prover places the cards according to the solution, faced down.
- For each row, column and subgrid, the verifier
chooses (at
random) one of the three cards of each cell in the corresponding
row/column/subgrid. and makes packets out of the chosen cards.
I.e. he assembles the
cards chosen for that row, columns or
subgrid.

- The prover
shuffles each of the 27 packets
separately, and
hands the shuffled packets to the verifier.

- The verifier
turns over all the cards in each
packet,
and
verifies that in each packet all numbers appear.

The soundness error of this protocol (the probability that a cheating prover succeeds) is 1/9. The protocol is zero-knowledge: for any verifier there exists a simulator that produces the same distributions of views that the verifier produces.

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.