The Envelope Please....

Two managers have run into a delicate problem. Each has received a complaint from a company employee on a sensitive matter. In both cases, the complainer has requested to keep his identity confidential. The managers would like to determine whether the same person has complained to both of them, but how can they do this without revealing to each other their complainers' identity?

A new cryptographic method for comparing sensitive information without sharing it has been developed by Prof. Moni Naor of the Weizmann Institute's Applied Mathematics and Computer Science Department, together with Dr. Ronald Fagin of the IBM Almaden Research Center in San Jose, California, and Dr. Peter Winkler of Bell Laboratories in Murray Hill, New Jersey.

The method may be applicable in a wide variety of situations when two parties wish to determine if they are in possession of the same information without revealing anything they know.

In our example of the two managers who received a confidential complaint, the method, called the Envelopes Solution, would work as follows:

●Each manager encodes the name of his complainer as a fixed-length sequence of 0's and 1's according to a predetermined method. For example, if "b" is encoded as 01 and "o" as 11, then Bob would be encoded as 011101.

● Next, each manager picks two random numbers for each slot in the sequence, one for 0 and the other for 1, writes each number on a separate note and puts the notes in a pair of sealed envelopes labeled '0' and '1'. If the sequence is six digits long, there would be six such pairs.

● The managers then exchange their sets of envelopes.

● Each manager then picks from each pair of envelopes one envelope that corresponds to the appropriate slot in his sequence. For example, if the sequence is 011101 (Bob), he picks the envelope labeled '0' from the first pair, the envelope labeled '1' from the second pair, and so on for the rest of the sequence.

● Each manager then opens the envelopes he picked and sums up the numbers written on the notes. The entire process is performed in full privacy, so that neither of the managers can see which envelopes the other picked. Care must also be taken that neither manager selects more envelopes than he should.

● Next, each manager repeats the procedure using his own numbers. When done with that, he adds up the two sums - the one he obtained while using his colleague's envelopes and the one obtained while using his own numbers - to obtain one sum total.

● Now the managers compare their sum totals. If they are different, they conclude they are dealing with two different complainers. But if the sum total is the same, there is a very high probability that they received a complaint from the same person. Importantly, in both cases the comparison of the sum totals reveals no information about the complainers' names.

The Envelopes Solution can be implemented digitally, without requiring that the two parties be physically present in the same room. The resulting type of cryptographic protocol, known as secure function evaluation, can be used for maintaining privacy in areas ranging from personal computer communications to banking transactions to national security. (A popular paper, "Comparing Information without Leaking It," is available. See also http://www.wisdom.weizmann.ac.il/~naor/puzzler.html.)