<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Thu, 20 Aug 2015 at 22:33 Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Thu, Aug 20, 2015 at 7:40 AM, Ian Goldberg <<a href="mailto:ian@cypherpunks.ca" target="_blank">ian@cypherpunks.ca</a>> wrote:<br>
> On Wed, Aug 19, 2015 at 10:49:50PM -0700, Trevor Perrin wrote:<br>
>><br>
>> It's nice to see people looking at this, but I agree with Moxie (and I<br>
>> think you) that a scaleable solution based on PIR or PSI doesn't seem<br>
>> to exist.  From the paper you cite:<br>
>><br>
>> <a href="http://eprint.iacr.org/2015/634.pdf" rel="noreferrer" target="_blank">http://eprint.iacr.org/2015/634.pdf</a><br>
[...]<br>
>><br>
>> In other words, the communication overhead is worse than the trivial<br>
>> PIR of sending a compressed list of users to the client = O(n1).  For<br>
>> n2=256, n1=2^24, their example protocols send hundreds of MB.<br>
><br>
> But for numbers that small, why *can't* you do actual PIR?  The database<br>
> will be of size ~1 GB, and if you're looking up 256 records in it, the<br>
> client will upload 256 * sqrt(2^30) B = 8 MB to the server, and download<br>
> the same amount.  The computation time on the server will be a bit<br>
> annoying: ~120 (highly parallelizable) core-seconds, but it's only done<br>
> once per new client, right?<br>
<br>
I think to be practical here computational PIR would need to handle<br>
something like:<br>
<br>
  1B users (e.g. phone numbers or email addresses) in system<br>
  1K users = average address book size<br>
  1% of users join or leave system each day<br>
  1% of address book entries change per day<br>
  1B queries per day (one per user)<br>
  100 queries per core per second (on server)<br></blockquote><div><br></div><div style="font-size:13.1999998092651px;line-height:19.7999992370605px">The rest of your numbers I can mostly agree with, but where does this one come from?</div><div style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div><div style="font-size:13.1999998092651px;line-height:19.7999992370605px">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.</div><div style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div><div><span style="font-size:13.1999998092651px;line-height:19.7999992370605px">Are you saying the system has to be sized to 100 cores? If so, why?</span></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  1 second query response for mobile client (including communication)<br></blockquote><div><br></div><div><span style="font-size:13.1999998092651px;line-height:19.7999992370605px">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.</span></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
If anything could meet these numbers I'd like to hear about it.<br>
<br>
Trevor<br>
_______________________________________________<br>
Messaging mailing list<br>
<a href="mailto:Messaging@moderncrypto.org" target="_blank">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
</blockquote></div></div>