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
David Jablon (dpj@world.std.com)
Wed, 06 Jan 1999 23:52:25 -0500
I've been interested in this question for the special
case where the secrets are small or guessable.
At 07:02 PM 1/6/99 +0100, Anonymous wrote:
> 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 [in case they don't match].
This related problem raises the question of what can be
done when the strings are small, or perhaps big but
confined to a small set.
> 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.
On the contrary, that one-to-one test is easy ... at least
if you trust in computational complexity. Try EKE or SPEKE.
Fagin, Naor & Winkler's paper has an interesting discussion,
but it's a poor reference for solutions. Their oblivious transfer
method is cumbersome, and surpassed by the (uncited) prior
work of Bellovin & Merritt, Gong, Lomas, Needham & Saltzer,
and other subsequent efforts.
<http://world.std.com/~dpj/links.html> points to several
papers on better one-to-one proofs of small knowledge.
This still leaves interesting questions of what can
be done, efficiently, to prove knowledge of 1 out of N
secrets. This may be interesting in both the cases of
of large and small secrets, and in both the cases of
revealing, or not revealing, which secret is selected
to the verifier.
But here are two more obvious limits:
1) Any non-leaking proof of small knowledge must be interactive.
2) If multiple runs are allowed, and the secrets are small,
regardless of the method used, Bob can mount a partition
attack to determine which one of N small secrets
Alice is proving knowledge of. He can do this in log_2(N)
runs, by committing to a series of specially constructed
different half-sets.
-------------------------
David P. Jablon
Integrity Sciences, Inc.
dpj@world.std.com
<http://world.std.com/~dpj/>
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:02