[messaging] Encrypted Pulic Contact Discovery

[Jeff Burdges]

On Thu, 2015-08-20 at 14:33 -0700, Trevor Perrin 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)
>   1 second query response for mobile client (including communication)
> 
> If anything could meet these numbers I'd like to hear about it.

I suppose the 1 query per user assumes very good caching.  


I've a question around this subject : 

Is there a good analysis of fibering PIR schemes?  My naive intuition is
that fibering any PIR scheme breaks it horribly.  And asymptotically
breaks it catastrophically. 

A priori, it's believable that some good mixnet designs could always get
slightly stronger as you add users, while PIR schemes need fibering and
become weaker, so that some good mixnets are always stronger for enough
users. 

It's tricky though because there is more than one way to fiber a PIR
scheme, maybe I simply don't know the right way to do so.  Also, there
are PIR schemes like Pynchon Gate that seemingly scale linearly in
bandwidth, and only pay the super-linear cost in computation, so maybe
they can be fibered better. 

Jeff

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150821/ad69994f/attachment.sig>