Comparing Information Without Leaking It

This is a rather open-ended question. However, we can judge a proposed solution according to these criteria who may not be all simultaneously achievable.

• Resolution - Ron and Moshe should find out whether or not their values match.
• Leakage - Assuming they follow the protocol faithfully, Ron and Moshe gain no knowledge about each other's value, except whether or not they are equal.
• Privacy - No one else should gain any information about Ron and Moshe's values. (e.g. a third party).
• Security - Neither Ron nor Moshe should be able to profit by cheating. That is, by failing to the follow the protocol, neither should be able to determine the other's value without matching it, or to determine whether the values match while denying that information to the other.
• Simplicity - The protocol should be easy both to implement and understand; that is, Ron and Moshe should be required to expend only a small amount of time, energy and money to learn, use and be confident of the protocol.
• Remoteness - Ron and Moshe need not be physically present at the same place in order to execute the solution.

Cryptographic research on this problem (and the more general problem of ``secure function evaluation") has been very fertile. The resulting solution are quite satisfactory in all the above criteria except for simplicity. Try and think of a simple solution that ranks high on as many properties as possible. Ron Fagin, Moni Naor and Peter Winkler have collected and evaluated many proposals in this paper (Abstract, Postscript, gzipped Postscript). A more technical paper on a related subject written by Uriel Feige , Joe Kilian and Moni Naor is available (Postscript, gzipped Postscript). We would be glad to hear of any different proposal.

A (favorite) solution

Back to the puzzle

Back to the Puzzler page