A man presents himself as the The Amazing Sand Counter. He claims that if you put some quantity of sand into a bucket, he will know at a glance how many grains there are, but he won’t tell you the number. Can you devise a test that can verify this ability without telling you anything that you don’t already know? You can ask the Sand Counter to leave the room or turn away, for example, and you can ask him questions. How can you convince yourself that he knows how many grains of sand are in the bucket when he won’t actually tell you the number?
|
SelectClick for Answer |
This is from Dennis Elliott Shasha’s 1992 book Codes, Puzzles, and Conspiracy, via Barry Cipra’s 2004 collection Tribute to a Mathemagician. Shasha wanted to find the simplest possible zero-knowledge proof — a proof in which a Prover convinces a Verifier that the Prover knows something without ever revealing the thing itself.
Shasha’s solution is this: Fill the bucket with sand, display it to the Sand Counter, then ask him to leave the room. Remove some countably small number of grains. When the Sand Counter returns, ask him how many grains have been removed from the bucket. Then count the removed grains to verify this. “The Verifier can repeat this test until he is convinced that the Sand Counter is either incredibly lucky (zero-knowledge proofs are often probabilistic in nature) or is telling the truth,” Shasha writes.
This actually works both ways — it also convinces the Sand Counter that the Verifier knows the total number of grains in the bucket, even though he has never revealed it. “The Sand Counter is happy to answer these questions as long as the number of grains removed is tiny compared to the number in the bucket,” Shasha writes. “This way he can be sure that the Verifier has learned how many grains there are.”
|
