Comparing Information Without Leaking
It
Ron Fagin, Moni Naor and Peter Winkler
Abstract:
We consider simple means by which two people may determine whether they
possess the same information, without revealing anything else to each other
in case that they do not.
We 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.
Postscript , gzipped
Postscript .
Apeared in: Communications of the ACM, vol 39, May 1996, pp. 77-85.
Back to On-Line Publications
Back Home