Puzzle 2
May 7, 2012, 5:48 pm
Filed under: Uncategorized | Tags: ,

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

The rules need to be made more definite to avoid ambiguity – Can the prover exchange one of the cups for his own behind the screen? Can he add/remove pebbles from the two cups? etc.

Comment by Anonymous

Yes the prover can do any of these things. She can do anything you could physically do in this situation with cups, pebbles and a screen.

However, note that the prover is trying to prove something about the original number of pebbles in the two cups initially on the table. Thus, it’s bad for her to take these two cups behind the screen, since then the verifier can’t be sure that the prover hasn’t somehow changed the number of pebbles in these cups.

Comment by Jared

Hmm, the verifier can see everything perfectly if it occurs in front of the screen?

I’d guess this involves some clever numeric property because the prover’s manipulation of the initial cups has to be transparent. (Though maybe I’m just tired at the moment; I’ll try again tomorrow. : ] )

Comment by Lucas Cook

There’s no difficult mathematics. Here’s a hint: the prover can put pebbles in cups behind the screen and then pour the contents of these cups into the cups already on the table.

Comment by Jared

(hmm I think my comment was accidentally eaten. Here’s a rewrite…)

That allows P to add a secret amount to any visible cup, but it seems that P must reveal the quantities whenever he modifies the original counters. If not, V might think that P is covering up their inequality. This is problematic for my current idea:

Each round, split initial cup1 into k cups c11, c12, …, c1k, and do the same for cup 2 into c21, c22, …, c2k such that c1i = c2i and each is nonempty. Then allow V to verify less than k of the cups for equality. Repeat as necessary.

This protocol reveals a lower bound on the quantity (and perhaps more as the game is repeated).

My problem is that I can’t reliably construct the c1i and c2i without counting things in the open.

Comment by Lucas Cook

Lucas, This is an interesting idea. It might be easier though to *add* secret amounts to the two initial cups and then reveal the contents. The hard part is how you can convince the verifier that you’re adding the same amount to both cups.

Comment by Jared

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: