The Secret in the Envelope
A new cryptographic method for comparing confidential information without disclosing it was developed by Prof. Moni Naor at the Weizmann Institute, 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 could be used in a wide variety of situations where two parties want to find out whether they have the same information without disclosing its content.
An example: Two managers face a tricky problem. Both received a letter of complaint from an employee under seal of confidentiality. In both cases, the author asked that his identity be kept secret. However, managers would like to verify that the sender is the same without revealing the employee's identity to the other.
In this case, the method called Envelopes Solution would work like this:
1.
Each manager encodes the sender's name as a fixed-length code consisting of ones and zeros according to a predetermined method. For example, if the letter "b" were encoded as 01 and "o" as 11, the name "Bob" would appear in the code as 011101.
2.
Next, each manager chooses two random numbers for each place in the digit sequence, one for 0 and one for 1, and then writes each number on a separate piece of paper and places them in a pair of envelopes labeled 0 and 1 becomes. If the sequence is six numbers long, i.e. has six places, then there are now six pairs of envelopes.
3.
The managers exchange envelopes.
4.
Each manager chooses the envelope from each pair of envelopes that fits the slot in his sequence. For example, if the sequence is 011101 (Bob), he selects the envelope marked "0" from the first pair, the envelope marked "1" from the second pair, and so on until the end of the sequence.
5.
Each manager then opens the envelopes he has chosen and calculates the sum of the numbers written in the envelopes.
6.
In the next step, each manager repeats the procedure with their own numbers. When that's done, he adds the two totals – the one he got from his colleague's envelopes and the sum he got from his own numbers to get a grand total.
7.
Now the managers compare their totals. If they are different, they can conclude that they are dealing with two different senders. However, if the total of both is identical, there is a very high probability that the complaint came from the same person. Regardless of the outcome, the comparison does not allow any conclusions to be drawn about the names of the people.
The envelope solution can be applied digitally without the two parties having to be physically in the same room. The resulting cryptographic protocol, called secure function evaluation, can be used to protect privacy and data protection in various fields - from communication between PCs to bank transactions and state security.
