[messaging] Encrypted Pulic Contact Discovery
trevp at trevp.net
Thu Sep 3 23:06:33 PDT 2015
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
> 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.
More information about the Messaging