[p2p-hackers] Oblivious information dispersal?

[Michael J. Freedman]

On Sun, 28 Aug 2005, Paul Campbell wrote:

> PIR also adds significant computational overhead and I just haven't seen a
> similar head-on comparison which doesn't get into really ridiculous amounts of
> bandwidth, although potentially it could be competitive.

The main goal of PIR schemes is o(n) bandwidth overhead, where n is the 
size of the database.  (Otherwise, a linear-bandwidth PIR solution is 
trivial:  send the entire database.)  In '99, Cachin, Micali, and Stadler 
presented the first polylog PIR scheme.

   http://citeseer.ist.psu.edu/cachin99computationally.html

Much more recently (ICALP 2005), Gentry and Ramzan presented a PIR scheme 
with constant bandwidth.

Still, a *costly* part of PIR schemes is the computation overhead (which 
is generally linear in the size of the database), not the communication 
overhead which protocols have mostly sought to minimize.

> In my mind, this could potentially do two things. First, it would be yet
> another route to do PIR...users could directly make queries but since the
> nature of the query is spread out over a dozen or more nodes, and the bits
> by themselves are fractional, it's still not possible to tell computationally
> what the goal of the query is. Second, it makes plausible deniability very
> easy to achieve...the database itself can't really tell what's in it's own

All of these protocols above, and actually what I think this thread has 
centered about, are about computationally-secure single-server PIR.

In fact, most work in PIR has focused on info-theoretically-secure 
multi-server PIR, in which databases are replicated across multiple 
servers, and the protocol is effectively taking XORs of various shares of 
the servers to recombine into the original data.  Still, the best results 
to date are not yet really practical.

   http://www.cs.technion.ac.il/~yuvali/pubs/BIKR02.ps

What I think you are proposing is a more ad-hoc technique that these 
protocols:  Given a file, break it up into shares (by a secret sharing 
scheme, for instance, or just XORing random bits) and spread those shares 
across servers.  Or, to add more "plausible deniability" by making those 
shares not linked to any specific file, mix the shares from various files 
together, so that Britney and the Declaration of Independence can both be 
regenerated from some share s_i.  Some examples of such systems include:

   Private message service
     http://www.inf.fu-berlin.de/~berthold/publ/BCKP_02.pdf
   Tangler
     http://www.cs.nyu.edu/~waldman/tangler.ps

See the related work in these papers for more citations.

However, the general difference between these proposals and PIR---and 
similarly between MIX/proxy-based schemes and PIR as well---is that the 
latter's security is formally provable via traditional reduction-based 
techniques, while the former's security is ad-hoc and ill-defined.  Of 
course, this formal security comes at the cost of performance.

--mike


-----
www.michaelfreedman.org                         www.coralcdn.org