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
Greg Rose (ggr@qualcomm.com)
Wed, 06 Jan 1999 05:57:36 +1000
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.
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. This isn't a true ZKP, but I think it solves
your problem. For further details, you'll need to do a search (and when you
finish, please remind me what it's called).
Greg.
Greg Rose INTERNET: ggr@Qualcomm.com
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01