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 05:58:38 +0100
This message is almost(?) incoherent. I will try to post a clearer follow-up.
At this point, there are two problems here:
I. Performance: The provee has to make multiple new masks for the Bloom test
every stinking time, or one with multiple "probes." It's barely feasible for a
set the size of my Rolodex, and I don't even *have* a Rolodex. :)
II. Active corruption: Although a corrupt provee that spits out the right bits
gains no info from the transaction, an actively corrupt one could gain
information by spitting out the wrong ones. The prover can ensure with some
degree of confidence that corruption would be detected, but that requires much
bandwidth and doesn't work well anyway. I say it doesn't work well because it's
largely useless if the provee has an idea which element is about to be used: a
provee that knows which element will be used can extract a "confession" of its
use from the prover, for instance.
III. Not real ZK: It's dependent on all sorts of computational assumptions, and
may leak stuff.
IV. Not thought through: I had to go to sleep; neither the protocol or its
description are sufficiently fleshed out.
(Yes, that's two problems :)
-------------------------------------------------------------------------------
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.
For the benefit of those trying to make a useful protocol from this, I will
later explain my awkward terminology and the properties of the Bloom filter
which make this system possible (and those that make it infeasible :).
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:02