Comparing Information Without Leaking
It
Discussion
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