In part 1 of our zero-knowledge proof series, we explained how a zero-knowledge proof could work when the verifier and the prover interact with each other.
An interactive zero-knowledge proof has the advantage that only the verifier can be absolutely convinced that the prover has the knowledge. But this can also be a disadvantage.
If bystanders and observers can’t verify the claim, the prover then has to interact with every verifier independently—which takes time and is resource intensive.
In this, part 2 we will look at non-interactive zero-knowledge proofs.
Non-interactive zero-knowledge proofs
The reason for non-interactive zero-knowledge proofs is to allow a large number of observers to verify the proof efficiently.
We do not always need to make zero-knowledge proofs non-interactive. Often enough it is possible to find a trusted verifier, who vouches for the integrity of the proof.
Non-interactive zero-knowledge proofs example: Sudoku and playing cards
Sudoku is a game with varying difficulty but relatively simple rules. Each of the 9 rows, 9 columns, and 9 sectors (as indicated by the thick black line) must contain each number from 1 to 9 exactly once.
Imagine that the solution to a sudoku puzzle is particularly hard to obtain, and takes days for even a supercomputer to compute.
But somebody (the prover) claims to have the solution to the puzzle and is willing to sell it for a price. How can they prove they have the solution—without revealing it—so the verifier is prepared to make payment?
The proof:
The prover needs 27 playing cards (of any suit) numbered 1-9—243 in total.
Now, the prover puts three cards with the number corresponding to the correct Sudoku solution in every box. E.G., if the correct answer for the box is 7, the prover will put 3 playing cards with the value of 7 in it.
On a Sudoku table, some answers will be visible. On these, answered boxes, the playing cards are placed face up. On the Sudoku boxes that are empty, the cards are placed face down.
To prove the facedown cards are all in the right position (without revealing the solution), the prover must:
- Take the top card from every row and make 9 piles
- Take the top card from every column and make 9 piles
- Take the remaining cards from every sector and make 9 piles
Each pile is then shuffled and turned around.
Every number between 1-9 must appear in every Sudoku row, column, and sector. So if every pile of the prover’s cards (from the row, column, and sector piles) contains each playing card valued 1-9, we know that they must have the solution.
Applications for Zero-knowledge proofs
Admittedly, the relatively young field of zero-knowledge proofs has not yet found the acceptance that it may deserve. They might, however, prove to be highly valuable.
Many mathematical problems are similar to a Sudoku puzzle (for example the Graph Coloring problem). If we can use the above principle and successfully apply it to a variety of problems, we might be able to use and trade computational resources and mathematical problems more efficiently. Or perhaps solve mathematical quandaries quicker.
Kudos to Ronen Gradwohl, Moni Naor, Benny Pinkas, and Guy Rothblum
