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 20:10:26 +0100
That is an interesting protocol, but it may not be appropriate for
the current problem.
As you say, any Bloom mask approach is inherently inefficient. It would
be more communication-efficient for B to send the entire contents of
his list to A. (The contents of the list are not secret, apparently.)
We are talking about a million to a billion items.
(Greg Rose's proposal for a Bloom mask had A send her mask to B. This
is presumably extremely sparse and so can be sent efficiently.)
Preventing corrupt behavior is not really practical in this context.
B can always substitute fake list items, and A can run her part of the
protocol with both a real and a fake secret, giving B the results for
her fake secret. We probably need to assume that both parties can be
trusted to follow the protocol.
One thing which was not clear from the original description is whether one
party has a greater interest in learning the result of the calculation.
One possible application is some kind of double spending detection, where
a secret value represents money and you don't want the bank to know the
value until you deposit it, but you want to make sure it is not on the
list of already-deposited values. In that case A is the one interested
in the output.
>A has the element; B has the set. A and B choose random numbers. B sends A the
>hash of its random number, and A sends B a random number. B hashes A's random
>number with its own to produce a seed for a PRNG. Each round uses a different
>"random" value from the keystream. Instead of seeding the PRNG used in Bloom
>test mask creation with the elements of the set, the element *and* the round's
>"random" value are used. B tells A the "value" and mask, but the mask sent is
>only the real mask half the time; the other half of the time, it's the bitwise
>inverse of the mask (0s->1s and 1s->0s). When to invert the mask is determined
>by the stream cipher's output so that it can be checked later.
>
>The Bloom test parameters must be set so that the mask looks almost exactly
>like randomness (i.e., proper 0/1 proportion), which can be done by setting the
>mask length and, for fine tuning, adding elements to the set.
>
>With B legit, fake As fail a round half the time, but legit As always pass (the
>inverted mask always fails the Bloom test).
>
>After receiving the challenges, A uses its knowledge of a secret to produce a
>set of set of "inverted/not inverted" results and hashes it with a new random
>number. It then sends the hash to B, and B sends its random number from the
>start of the protocol to A. A uses this to verify that the (still unsent)
>results are correct.
>
>If A finds that A's (currently unsent) results are correct, A reveals the
>results and random number, and B checks the "inverted/not inverted" results and
>the hash; if they both check, A has knowledge of the secret. If, during the
>checking mentioned in the above parapgraph, A discovers that the results are
>not correct, A either does not know the secret or was almost a victim of an
>actively corrupt B. Either way, A would at that point run away from the deal
>without having proven knowledge of the secret, but also without having given
>any information to B.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:02