Two Envelopes, Please

January 19, 1998

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.)

ADDITIONAL INFORMATION

Prof. Naor holds the Morris and Rose Goldman Career Development Chair.

The Weizmann Institute of Science, in Rehovot, Israel, is one of the world's foremost centers of scientific research and graduate study. Its 2,500 scientists, students, technicians, and engineers pursue basic research in the quest for knowledge and the enhancement of the human condition. New ways of fighting disease and hunger, protecting the environment, and harnessing alternative sources of energy are high priorities.

Weizmann Institute news releases are posted on the World Wide Web at http:\\www.weizmann.ac.il and also at http:\\www.eurekalert.org.

The American Committee for the Weizmann Institute is seen at http://www.weizmann-usa.org
-end-


American Committee for the Weizmann Institute of Science

Related National Security Articles from Brightsurf:

Men less likely to see food as national security issue amid pandemic
On average, men not only showed less empathy toward temporary agricultural laborers but also were less likely to see food supply and production as national security issues, according to a study led by a Washington State University researcher.

National trash: Reducing waste produced in US national parks
When you think of national parks, you might picture the vast plateaus of the Grand Canyon, the intricate wetlands of the Everglades, or the inspiring viewscapes of the Grand Tetons.

UBC study: Publicizing a firm's security levels may strengthen security over time
New research from the UBC Sauder School of Business has quantified the security levels of more than 1,200 Pan-Asian companies in order to determine whether increased awareness of one's security levels leads to improved defense levels against cybercrime.

3-D printing of weapons threatens security on global, national and personal level
A new RAND Corporation paper suggests additive manufacturing could benefit military adversaries, violent extremists and even street criminals, who could produce their own weapons for use and sale.

National Academies review of the draft Fourth National Climate Assessment
The US Global Change Research Program (USGCRP) asked the National Academies of Sciences, Engineering, and Medicine to review the draft Fourth National Climate Assessment (NCA4) -- a congressionally mandated report that evaluates the state of climate science and the broad range of impacts of climate change in the United States every four years - and the draft Second State of the Carbon Cycle Report (SOCCR2) - a report that feeds into the overall assessment process developed by USGCRP.

Morgridge, UW scientists explore national security implications of gene editing
A trio of scientists from the University of Wisconsin-Madison and the Morgridge Institute for Research participated in an international think tank this month on the intersection of genome editing technology and national security.

Installing solar to combat national security risks in the power grid
Power grid vulnerabilities are one of the most prevalent national security threats.

Bring your own (security) disaster
Bring your own device (BYOD) to work is common practice these days.

Blurring of national security interests & global health agendas are an unavoidable reality
Society must align the overlapping priorities and often clashing interests of medical intelligence, national security agendas and the global health community, according to global health advocates writing in the Journal of the Royal Society of Medicine.

Steve Elgar named National Security Science and Engineering Faculty Fellow
Steve Elgar, a senior scientist at Woods Hole Oceanographic Institution, has been selected as a 2016 National Security Science and Engineering Faculty Fellow by the Department of Defense.

Read More: National Security News and National Security Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.