[messaging] Encrypted Pulic Contact Discovery

[Ian Goldberg]

On Wed, Aug 19, 2015 at 10:49:50PM -0700, Trevor Perrin wrote:
> On Wed, Aug 19, 2015 at 6:17 PM, Daniel Reichert <daniel1555 at gmail.com> wrote:
> > Private Set Intersection has come a long ways since 2009.  Just this year a
> > paper[1] was published where private contact discovery is a primary use
> > case.  Detailed benchmarks for varying sizes of the client and server set
> > sizes are included.  Sadly it's still not practical since the only way to
> > prevent a brute force search requires making the protocol O(n1*n2) where n1
> > is the client set size and n2 is the server set size.
> 
> It's nice to see people looking at this, but I agree with Moxie (and I
> think you) that a scaleable solution based on PIR or PSI doesn't seem
> to exist.  From the paper you cite:
> 
> http://eprint.iacr.org/2015/634.pdf
> """
> Private contact discovery
> [...]
> In these cases each user has a small number of records n2, e.g., n2 =
> 256, whereas the service has millions of registered users (in our
> experiments we use n1 = 2^24). It therefore holds that n2 << n1. In
> our best PSI protocol, the client needs only O(n2 * log n1) memory,
> O(n2) symmetric cryptographic operations and O(n1) cheap hash table
> lookups, and the communication is O(n1 *
> log n1).
> """
> 
> In other words, the communication overhead is worse than the trivial
> PIR of sending a compressed list of users to the client = O(n1).  For
> n2=256, n1=2^24, their example protocols send hundreds of MB.

But for numbers that small, why *can't* you do actual PIR?  The database
will be of size ~1 GB, and if you're looking up 256 records in it, the
client will upload 256 * sqrt(2^30) B = 8 MB to the server, and download
the same amount.  The computation time on the server will be a bit
annoying: ~120 (highly parallelizable) core-seconds, but it's only done
once per new client, right?  (Both the bandwidth and computation will be
a little less for Chor-like non-robust multi-server PIR, and a little
more for single-server CPIR.)

   - Ian