The following puzzle is supposed to have applications in treaty verification.
There are two people playing a game: a prover and a verifier. There is a table between the two people, and on the table are two cups, each with some number of pebbles in them. The prover also has an unlimited supply of cups and pebbles, and a screen she can use to hide activity on her side of the table.
The goal of the game is for the prover to prove to the verifier that the two cups originally on the table have the same number of pebbles in them, but to not reveal the number of pebbles in either of these cups.
How can you ensure that the verifier can be sure that the two original cups have the same number of pebbles with any arbitrarily small probability of error? What is the most efficient protocol you can devise to accomplish this goal? Here efficiency is measured in terms of time (number of rounds) and communication (number of cups), versus the probability with which the verifier can be sure that the two original cups have the same number of pebbles.
6 Comments so far
Leave a comment