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:01
Ryan Lackey (ryan@venona.com)
Tue, 5 Jan 1999 12:00:51 -0400
I've been looking at something, and a really cool feature seems to
depend on the following test:
"Without revealing more than a single bit of information to party A
or party B (the set membership status of the item), is it possible to test
if a 1024-bit string on A's personal computer is contained in a list stored
on B's personal computer, in (preferably) a small number of network and
compute steps or (failing that) a vaguely tractable/finite computation,
not involving a TTP." The list on B's computer contains 10E6-10E9 elements.
I know the answer is "yes" if you do secure multiparty computation.
What I'd really like is a very efficient set-member
predicate in zero-knowledge. I'd search for this myself, but I presently
don't have access to a library (the local pub on Anguilla has about
as many books as the official library...).
Failing zero knowledge, I'd be willing to reveal some small number of bits
from A to B, on the order of 10 bits.
Failing that, it might be acceptable to reveal any of B's
bits, but for efficiency reasons (since B's list is huge), revealing
all of B's bits is kind of difficult.
I can think of some of the simple approaches, but there *has* to be
a trick I'm not remembering to this problem.
Thanks,
Ryan
ryan@venona.com
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01