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
Anonymous (nobody@replay.com)
Tue, 5 Jan 1999 21:01:30 +0100
> "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.
This is not suitable for a zero knowledge protocol, since in ZK we assume
one side has all the necessary information, and wants to prove some fact
to the other side. In this case, each side has part of the information.
You are inherently asking for an MPC protocol.
You could look into using an ANDOS protocol to do this. ANDOS is "all
or nothing disclosure of secrets", a generalization of two string Oblivious
Transfer.
The idea is that Bob will give Alice one element from his list, an element
which she selects, but he will not find out which element it is. So if
Bob had ten items, Alice could ask for and receive number 4. Bob would
know that she got one of the items, but he would not know that it was
number 4, and Alice would not learn anything about the other items.
There was a relatively efficient ANDOS protocol presented at AsiaCrypt 98.
I don't know if the paper is on the net; you could ask the author for
a copy. His name is Julien P. Stern, a copy. His name is Julien P. Stern, stern@lri.fr. If you want, I can
describe the protocol in about a page, along with some optimizations
that you could use, but in that case you will have to say more about
what your application. Quid pro quo.
To use this protocol, you would want to choose a limit N large enough that
it is guaranteed that no two secrets would have the same value mod N.
It would have to be about the size of the square of the maximum number
of list elements, because of the birthday paradox.
Bob would create a binary vector, where index i was 1 if a list element
was congruent to i mod N, else 0. Alice uses the ANDOS protocol to get
item "s mod N", where s is her secret. If the result is a 1, her secret
is in the list.
While this protocol is more efficient than some older ones, it is probably
not going to be that much better than just sending the whole list over.
Sending the whole list over would take 2^30 values times 2^10 bits or
2^40 bits. A quick look at the ANDOS protocol suggests that it would
take about 2^15 queries times 2^10 bits per query or 2^25 bits (these go
from Alice to Bob rather than in the other direction). There is also a
considerable computational load, about 2^31 640-bit modular multiplies.
In effect you are trading off communication for computation.
In short there may not be an efficient way to do what you want. It takes
a lot of work to do MPC well.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01