[messaging] Encrypted Pulic Contact Discovery

[Daniel Reichert]

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

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.

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

Daniel Reichert

[1]
https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/pinkas
[2]
https://www.usenix.org/sites/default/files/conference/protected-files/sec14_slides_pinkas.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150820/5beb8601/attachment.html>