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)
Wed, 6 Jan 1999 00:55:24 +0100
Giff writes:
>
> On Tue, 5 Jan 1999, Anonymous wrote:
>
> > If A's numbers are unguessable, as being 1024 bits suggests, can he just
> > send a hash of his number to B, and have B tell him whether the number is
> > in the list (by comparing to the hashes of list items)?
>
> No, because then B knows the number in question, since he calculates the
> hash for each of his numbers until he finds a match.
Oh I see. It would work OK if A's number were NOT in the list, but not
too well if A's number WERE in the list.
It seems like Greg's proposal has the same problem:
> Basically you take the data item in question and use it to seed a random
> number generator of appropriate characteristics. Then generate n outputs
> from it, interpret them as bit indexes into a large bitmap, and test if all
> of the bits are set. (Of course you seed the bitmap by doing this and
> setting the bits for all M members of the set.) The size of the bitmap N
> (and hence the range of the psuedo-random numbers), and number of probes n,
> must be chosen appropriately based on M and the desired probability of
> assurance. N is not that much bigger than the original data (certainly
> within an order of magnitude for any reasonable probability).
>
> It seems to me that if the PRNG is cryptographically secure, you can sort
> the outputs and compress them (by difference encoding) to come up with
> something which can't be forged and yet reveals nothing (computationally
> speaking) about its inputs.
If he intends that A (who has the number) is sending this "fingerprint"
to B (who has the list), then in case of a match, B can try all of his
numbers and see which of them produce that same pattern.
I don't think he meant that B is sending a bitmap to A that encodes
the values of his whole list, because that would probably be too big.
He could get the same effect by sending A a list of hashes of his entries,
where the size of his hashes is chosen to make the chance of a false
match be sufficiently low.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01