[messaging] Encrypted Pulic Contact Discovery

[Trevor Perrin]

On Fri, Aug 28, 2015 at 1:25 AM, Ben Laurie <ben at links.org> wrote:
>
> On Thu, 20 Aug 2015 at 22:33 Trevor Perrin <trevp at trevp.net> wrote:
>>
>> 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)
>
>
> The rest of your numbers I can mostly agree with, but where does this one
> come from?
>
> Clearly, the system has to handle ~10,000 qps as a whole. Using Ian's
> numbers, that would be 1.2M cores. Ouch! And actually, it would presumably
> be substantially worse because your numbers are a lot higher.

Yeah, I was proposing 2^30 registered users instead of Ian's 2^24.  I
think PIR cost on the server scales at least linearly with # of
database entries, because the server has to consider all of them per
query.  So I think the naive estimate would be 64x higher, so ~80M
cores?


> Are you saying the system has to be sized to 100 cores? If so, why?

It's a crude cost estimate - the more expensive this gets, the less
likely it gets deployed.

But precision isn't super important here as long as PIR techniques are
several orders of magnitude away.


>>   1 second query response for mobile client (including communication)
>
>
> Another number I would argue with - for a daily address book refresh, this
> could take substantially longer. Even if I were wanting the lookup live, it
> can take as long as it takes me to construct my message, at least.


Recipient selection is often done *before* composing a message.  For example:

 * User starts an app
 * User taps "Send new message"
 * Contact discovery happens while user waits
 * App displays the intersection of address book with registered users
 * User selects recipient(s) from intersection list
 * User composes message

Contact discovery delay here is very noticeable.

Trevor