Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:02
Anonymous (nobody@replay.com)
Wed, 6 Jan 1999 19:02:46 +0100
A couple of points have not been made clear in Ryan's statement of the
problem.
Is it OK if B finds out *which* number A matches, if a match occurs?
If so, then in case there is no match, is it OK if B is later able to
recognize when A's value was added? In other words, is it OK if B can
look for a match between a later set of values and an earlier query by
A?
The May, 1996 Communications of the ACM had an article by Fagin, Naor,
and Winkler on "Comparing Information Without Leaking It". This was a
similar problem, but where B has just one string. A and B want to know
if they have the same string, without either of them finding out what
string the other has (of course they do find out, in the event that
there is a match).
This paper can be found online by linking from
http://www.wisdom.weizmann.ac.il/~naor/onpub.html. It has many clever
approaches, but none seem to generalize very well to the n-string case.
If even doing the simple one-to-one match test is this hard, it is
unlikely that a many-to-one test is going to be easy.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:02