If you subscribe to the adage "seeing is believing," you may not like zero knowledge proofs. A zero knowledge proof is a two-person interaction in which a Prover P can demonstrate knowledge of some Fact F to a Verifier V without revealing F to V. Now, if you think some of your university math teachers were trying this in your differential equation classes, you are not alone.

In modern life, zero-knowledge proofs are used whenever someone uses public key cryptography to digitally sign a message. The sender S applies a decryption key D_s to the message m yielding D_s(m). Only S knows D_s, but everyone knows the corresponding public key P_s, so the recipient applies P_s(D_s(m)) to get m back. Only the possessor of D_s can have signed m in that way, so S proves that he or she knows D_s without revealing D_s. S convinces the receiver of S's possession of D_s without revealing D_s.

We will look at two zero knowledge proofs that require no cryptography, no fancy math — in fact, no computers. Here is the first problem.: You are presented with an opening Sudoku board having some numbers plugged in. You work on it.

You: "I've solved it."

Other: "Show me."

You: "No, you should trust me."

Other: "Why should I?"

You: "Ok, I'll prove it to you."

Other: "How?"

You: "I'll show you that every row has 1 through 9,every column has 1 through 9, every 3x3 Sudoku square (upper left, bottom left, middle left, etc.) has 1 through 9, and the numbers in the initial positions are what they should be."

Other: "That will be sufficient, but how can you do that without showing me the solution."

1. That is the problem. How can you prove that you have a solution without revealing that solution? Hint: use 81 cards.

If you were able to solve this problem, you understand the essential core of the zero knowledge idea as it applies here: You can prove that each row or column has 1 through 9 without revealing the order of numbers. What is remarkable in this case is that by revealing the set membership of an entire row, you tell NOTHING about the order in that row.

The general zero knowledge idea works in a similar way, but is often probabilistic. For example, suppose I claim that I can look at a bucket of sand and know how many grains there are. You may not believe me, but you can put me to the test easily enough. You ask me to leave the room and then...well, and then, you do what?

2. How would you test someone's ability to know at a glance how many grains of sand there were in a bucket without your learning anything about the number of grains that are in fact there?

A lot of problems in society could be resolved if we could find zero-knowledge ways to prove someone followed the rules without invading his privacy. For example, suppose we wanted to find out whether someone paid sufficient taxes without knowing what he or she paid.

Those are serious problems.

I would be satisfied with the solution to the following apparently simple variant of question 2, which I leave to you as an open problem. Suppose that you are convinced that the person does know how many grains there are in a bucket. Now he gives you a number. How would you test the truth of that number in time proportional to the log of the number of grains there are? To be concrete, counting a single grain, dividing the bucket into two approximately equal piles or pouring one pile over another each costs one time unit.

I have no idea how to solve the problem.