Peggy and Victor are competing on who can solve a certain Sudoku puzzle the fastest.
Sudoku rules:
fill a nine-by-nine grid with digits, such that each column, each row, and each of the three-by-three subgrids β called *boxes* β contains each digit from 1 to 9 exactly once.
After racking her brain for hours, Peggy finds the solution β and she's first!
Now, she wants to prove to Victor that she has indeed solved the Sudoku.
Peggy is a good sport, and she doesn't want to ruin the puzzle for Victor.
This means that she cannot just show the solution to Victor.
Peggy appears to be in a pickle.

Luckily, Peggy has recently heard of *Zero-Knowledge Proof Systems*.
They seem to be the perfect solution to her problem.
Peggy and Victor can use the card-based **zudoku** to convince Victor that Peggy knows the solution β and Victor won't get any hint about the solution.
Peggy is in the role of the *Prover*: she proves she knows the solution.
Victor's role is called *Verifier*, since he checks whether Peggy really knows it.
These roles appear in every Zero-Knowledge Proof System, not just **zudoku**.

**zudoku** is immediately useful in proving knowledge of Sudoku solutions β obviously a very common problem.
Apart from that, it demonstrates that Zero-Knowledge technology is not (necessarily) magic.
**zudoku** is very intuitive and doesn't need any mathematics or programming.

# zudoku

The **zudoku** proof system is an *interactive protocol*.
**Z**ero-**K**nowledge + Sudoku β **zudoku**
That means Peggy and Victor have to play together for the entire thing to work.

Furthermore, Peggy needs some cards, all with the same back side. The front of a card shows one of the digits 1 through 9. Because Peggy will lay out her solution using the cards, she needs nine cards per digit.

Lastly, Peggy and Victor need the Sudoku puzzle they are playing **zudoku** with.
Victor has printed the puzzle and puts it before them.
Printing the puzzle is not necessary.
It just makes playing **zudoku** more convenient.

### setup

Peggy and Victor start with the setup for **zudoku**.
They use Peggy's cards to mimic the puzzle:
every digit printed on the grid is covered with a card showing the same digit, with the digit facing up.

When all printed digits are covered, the Sudoku essentially still looks the same, except that instead of Victor's print-out, Peggy's cards are used. This is why printing the Sudoku is not necessary β laying out the puzzle using the cards is enough.

### commit

Peggy puts the solution with her cards facing down into the free cells. She needs to make sure that Victor can't tell which card she puts where β otherwise she would be giving him hints!

### challenge

Now it's Victor's turn. Theoretically, he could just turn all or some cards around β but that way he'd learn something about the solution! Instead, Victor chooses whether he wants to check the Sudoku's rows, or the columns, or the boxes. Ideally, Victor's choice is as random as possible, for example by rolling a die: rolling 1 or 2 means checking rows, 3 and 4 mean checking columns, and 5 and 6 mean boxes.

Victor chooses to check the rows. He takes all nine cards in the first row, shuffles them, and turns them around. Then he checks that all digits, 1 to 9, are there β none missing, none double. Since Peggy has put the correct solution for the Sudoku, this is exactly what he finds.

Shuffling the cards makes sure that Victor does not know the position of a card on the board. This way, even after turning the cards around, he doesn't know anything about the solution.

He proceeds to the next row, takes the cards, shuffles them, then turns them around. Again, he checks that the rules of Sudoku are followed β all digits appear exactly once.

This way, Victor checks all rows.
It's very important that Victor sticks with his choice, and checks *only* rows, or *only* columns, or *only* boxes.
If, for example, Victor were to check a column after having removed the first row, he would have only eight cards.
One digit would be missing:
the digit where the checked column and the first row intersect.
This way, Victor gets a hint about the solution.
If, in any row, he were to find some digit twice, he would know that the rules of Sudoku were violated β which would mean that Peggy did not actually put the solution in the board!
But Peggy has put the real solution, so for every row, Victor finds every digit exactly once.

### repeat

Even though Victor has confirmed that Peggy has put her cards in a way that the rows comply with the Sudoku rules, he is not convinced yet. After all, the rules of Sudoku apply to rows, columns and boxes, not just to rows! He tells Peggy that he wants to go again.

As before, they set up the Sudoku puzzle by placing cards face-up on the printed digits, and Peggy lays in the solution face-down again. Now, Victor can make the same choice as before: check the rows, or the columns, or the boxes. Again, he verifies that the chosen sections comply with Sudoku rules by shuffling the cards and turning them over.

If Victor is still not convinced, he asks Peggy to go again. And again. And maybe one more time?

Because Peggy always puts the correct solution, no matter whether Victors chooses rows, columns, or boxes, he will always find that the rules of Sudoku are upheld.
After playing **zudoku** for enough rounds, Victor is finally convinced.
A Zero-Knowledge Proof System where an honest Prover can always convince an honest Verifier is called *complete*.

But why can he be so sure that Peggy didn't cheat?

## catching cheaters

The mischievous Mallory overheard Peggy and Victor perform **zudoku**.
Mallory is not a great Sudoku puzzler, and she does not know the solution.
However, she thinks that using **zudoku**, she can trick Victor into believing that she knows the solution.

Even though Mallory was not able to find the Sudoku's correct solution, she did prepare three βfake solutions.β These fakes are crafted in an attempt to fool Victor.

In Mallory's first fake, every digit appears exactly once per row, and also exactly once per column, but the boxes are all wrong.

The other two fakes are similar: in the second one, every digit appears exactly once per column and per box, but some digits appear twice or more in the rows. The third fake has inconsistent columns, but the rows and the boxes are fine.

Mallory and Victor start playing **zudoku**.
First, they perform the setup.
Now, Mallory needs to choose which of her fake solutions she wants to use.
She picks the fake where the rows and the columns are fine, but the boxes aren't, and puts the cards face-down in the grid.
Then she turns all remaining visible digits around.

Victor can now choose whether he wants to check rows, columns, or boxes. His decision is independent of Mallory's choice.

If Victor chooses to check the boxes, he will immediately realize that Mallory is cheating, call her out on it, and stop playing **zudoku** with her.
Should he instead choose to check the rows or the columns, he won't catch her in this round.
But no matter his choice, Victor is not convinced after just one round, so he asks Mallory to play again.
If they play for long enough, it is very likely that Mallory is caught.
After *n* many rounds, the probability that cheating Mallory is caught is 1 - (β
)^{n}.
For 4 rounds, that's 80%.
10 rounds gives over 98%.

After all, Mallory has to guess which section Victor will not check *before* knowing Victor's choice.
A Zero-Knowledge Proof System where a dishonest Prover can almost never convince an honest Verifier is called *sound*.
In fact, probably even Victor himself doesn't yet know what he will check, especially if he is rolling a die!
Once Mallory has made her guess, she cannot change the cards on the grid anymore β she is *committed*.
Correctly predicting Victor's choice β or the die β many times in a row is quite unlikely.
Technically, because there's a slim chance that Mallory is never caught cheating, **zudoku** is an *Argument* System, not a Proof System.

# credits

**zudoku** is based on this paper.
Ronen Gradwohl,
Moni Naor,
Benny Pinkas,
and Guy N. Rothblum:
βCryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzlesβ

It is essentially a card-based variant of Protocol 6.
The paper is a lot more explicit about the involved assumptions, and formally analyzes soundness errors.
It is a good start for further reading.

I first heard about the protocol presented here, as well as the name **zudoku**, from JΓΆrn MΓΌller-Quade, who introduced me to the marvelous world of crypto.
βCryptoβ means Cryptography.

The Sudoku that Peggy and Victor were competing over is βAI Escargotβ by Arto Inkala. It is reproduced here with his friendly permission.

This website is hosted on GitHub Pages, statically rendered by Jekyll, and uses the Basically Basic theme with margin notes from Tufte CSS mixed in.