Comparing Information Without Leaking It

A solution

Here is one of our favorite solutions suggested by Miki Ajtai of the IBM Almaden Research Center. His proposal is "physical" in the sense that Ron and Moshe must be together. We need to assume that there is a fairly small pool of candidates, say twenty. Ron and Moshe obtain twenty identical containers (perhaps by purchasing disposable cups (paper or plastic)), arrange them in a line, and write labels in front of each cup, one for each candidate. Ron then puts a folded slip of paper saying ``Yes'' in the cup of the person who complained to him, and a slip saying ``No'' in the other nineteen cups. Moshe does the same. Ron and Moshe then remove the labels, and shuffle the cups at random. They then look inside the cups to see whether one of them contains two slips saying ``Yes'' and decide accordingly.

Discussion and pointers

Back to the puzzle

Back to the Puzzler page