security
Zero-Knowledge Sudoku Proof
Interactive terminal demo of a zero-knowledge proof for Sudoku: the verifier opens rows, columns, and 3x3 boxes of a hidden solution one at a time, each shown only as a sorted list, until a chosen confidence level is reached.
Role
Developer — team project (3 students)
Problem
Hands-on exploration of zero-knowledge proof theory for advanced cryptography coursework: convince a verifier that a puzzle has a valid solution without showing the solved grid. The protocol is simplified. Revealed units are sorted rather than cryptographically committed, and the user at the terminal answers whether each revealed unit is valid.
Tech Stack
Python
How It Works
- 01main.py loads an unsolved puzzle, either from Sudokus2.txt or freshly made by Generator.py (a bundled third-party generator with easy, difficult, and possibly-unsolvable modes). pySudoku.py then solves it by filling forced cells and backtracking.
- 02The user sets a confidence percentage, and the prover splits the solved grid into 27 'packets': 9 rows, 9 columns, and 9 3x3 boxes.
- 03Only the unsolved puzzle is shown. Each round the verifier picks an unopened packet, and the prover shows its numbers sorted, so the digits can be checked without revealing where they sit in the grid.
- 04Verifier.py counts approved packets. The proof is accepted once approved/27 reaches the confidence level, and rejected if every packet is opened first.
What I Learned
- –Working through zero-knowledge proofs on a concrete example (Sudoku) made an otherwise abstract concept, proving knowledge without revealing it, actually click.
- –Splitting the code into separate Prover and Verifier classes mirrored how these roles are described in the literature, which made mapping theory to code much easier.
- –The simplified version made the gap visible: without real commitments, nothing stops a prover from answering each challenge inconsistently. That's why proper ZK protocols commit to a randomly permuted solution before any challenge.