On Thu, 20 Aug 2015 at 22:33 Trevor Perrin <[email protected]> wrote: > On Thu, Aug 20, 2015 at 7:40 AM, Ian Goldberg <[email protected]> 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 > [email protected] > https://moderncrypto.org/mailman/listinfo/messaging >
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
