<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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>
<span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><div><br></div><div>This is to due to PIR having a weaker security definition than PSI. Under PIR the client is allowed to learn more than the intersection of the client and server set. As you say it is acceptable under PIR for the client to learn the complete server set.  This is true even if they have zero elements in common. PIR only seeks to limit the information that the server can learn about the client set.</div><div><br></div><div>On the other hand the security definition of PSI requires that the privacy of both the client and server are maintained. The only information that each party is allowed to learn are the elements in their intersection.</div><div><br></div><div>I definitely agree that PSI protocols are a long ways from being practical at the scale of millions of users. I thought it would be of interest to point out that PSI protocols have recently made several orders of magnitude improvement in both computation and communication overhead.  See the video at [1] around the 13 minute mark or the slides directly [2].</div><div><br></div><div>Daniel Reichert</div><div><br></div><div>[1] <a href="https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/pinkas">https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/pinkas</a><br></div><div>[2] <a href="https://www.usenix.org/sites/default/files/conference/protected-files/sec14_slides_pinkas.pdf">https://www.usenix.org/sites/default/files/conference/protected-files/sec14_slides_pinkas.pdf</a></div><div><br></div></div></div></div>