|
|
|
|
|
|
|
|
|
|
|
|
| home | help | back | first | fref | pref | prev | next | nref | lref | last | post |
To: Greg Rose <ggr@qualcomm.com>
Cc: Ryan Lackey <ryan@venona.com>, cryptography@c2.net, coderpunks@toad.com,
cypherpunks@algebra.com
Date: Tue, 05 Jan 1999 17:06:51 -0500
From: Steve Bellovin <smb@research.att.com>
In message <4.1.19990106054310.00a919e0@127.0.0.1>, Greg Rose writes:
> At 12:00 5/01/99 -0400, Ryan Lackey wrote:
> >"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.
>
> There's a really neat technique, whose name I can't remember at the moment
> but it is quite old and well known, for doing probabilistic set membership
> tests.
It's a Bloom Filter, I believe.
|
|
|
|
|
|
|
|
|
|
|
|
| home | help | back | first | fref | pref | prev | next | nref | lref | last | post |