[messaging] Encrypted Pulic Contact Discovery

[Ben Laurie]

On Thu, 20 Aug 2015 at 22:33 Trevor Perrin <trevp at trevp.net> wrote:

> 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)
>

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.

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


>   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.


>
> If anything could meet these numbers I'd like to hear about it.
>
> Trevor
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150828/b076a595/attachment.html>