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:25
Anonymous (nobody@replay.com)
Wed, 3 Feb 1999 02:20:28 +0100
On January 5, Ryan Lackey, ryan@venona.com, asked:
> "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.
Most proposed solutions were inefficient or didn't satisfy the security
requirements.
Another approach would work if the list is stored on two different
computers, B and C, who don't communicate with each other. If Bob and
Carol both have copies of the database, there is a reasonably efficient
protocol which Alice can use to find out if her string is in the DB
without Bob or Carol finding out what string she has. However this
depends on Bob and Carol not colluding. If they do collude, they can
easily learn Alice's string (or at least part of it).
As in many crypto protocols where we want to control the spread of
information, things are actually easier when there are more parties
involved. This solution provides information-theoretical privacy to
Alice, not just computational privacy. Neither Bob nor Carol gets any
information whatsoever about Alice's string (again, stipulating that
they do not collude).
The protocol is reasonably efficient. For a list of 1 million elements
it requires about 35K bits of communication. The computational load is
tolerable, requiring comparisons of a substring of each entry in the list
against a set of matching bits sent by Alice. This can be done in just
a few passes if the list is pre-sorted. There is no exponentiation or
other large-integer arithmetic needed.
I won't try to give details here; the method is based on techniques
in http://www.cs.technion.ac.il/~eyalk/GIKM.ps.Z. You need to convert
the problem to a single-bit-retrieval problem and use the method called
S2 on page 5. The protocol appears to be based on an older 1995 paper
which is in the references.
The requirement to split the database among two non-colluding parties
may not be appropriate for this specific application, but the technique
is still interesting.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:25