Machinations

Puzzle 2 – A Partial Solution
May 16, 2012, 2:03 am
Filed under: Uncategorized | Tags: ,

So here’s one partial solution to the puzzle I described in my last post.

The prover sets up n pairs of cups behind the screen. For pair i, she places X_i stones in both cups, where X_i is a random variable uniformly distributed among the positive integers. Then she removes the screen.

Now the verifier chooses n-1 of the pairs of cups and asks the prover to reveal the contents. The verifier rejects the proof immediately if any of these revealed pairs have unequal numbers of stones.

Next, the prover takes each cup in the unrevealed pair and pours its contents into each of the cups in the original pair of cups in the table. Finally, the prover reveals the new contents of these original cups. If there are the same number of stones in each cup in the pair, the verifier accepts the proof, otherwise, he rejects it.

So this ensures that if the verifier accepts the proof, then the original pair of cups have equal number of stones with probability 1-1/n.  Moreover, the verifier learns little about the number of stones in the original pair.  It’s not perfect, since the verifier knows, for example, that the original number of stones is no more than the final number of stones.  (Of course, if you were doing this on a computer, you’d add the stones modulo some large number)

I’m interested in improvements to this algorithm.  Can the original number of stones be better hidden?  Can we decrease the probability of error as a function of the number of cups used?