[messaging] Encrypted Pulic Contact Discovery

[Trevor Perrin]

On Thu, Aug 20, 2015 at 7:40 AM, Ian Goldberg <ian at cypherpunks.ca> wrote:
> On Wed, Aug 19, 2015 at 10:49:50PM -0700, Trevor Perrin wrote:
>>
>> 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
[...]
>>
>> 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?

I think to be practical here computational PIR would need to handle
something like:

  1B users (e.g. phone numbers or email addresses) in system
  1K users = average address book size
  1% of users join or leave system each day
  1% of address book entries change per day
  1B queries per day (one per user)
  100 queries per core per second (on server)
  1 second query response for mobile client (including communication)

If anything could meet these numbers I'd like to hear about it.

Trevor