On Wed, Aug 19, 2015 at 6:17 PM, Daniel Reichert <[email protected]> wrote: > Private Set Intersection has come a long ways since 2009. Just this year a > paper[1] was published where private contact discovery is a primary use > case. Detailed benchmarks for varying sizes of the client and server set > sizes are included. Sadly it's still not practical since the only way to > prevent a brute force search requires making the protocol O(n1*n2) where n1 > is the client set size and n2 is the server set size.
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 """ Private contact discovery [...] In these cases each user has a small number of records n2, e.g., n2 = 256, whereas the service has millions of registered users (in our experiments we use n1 = 2^24). It therefore holds that n2 << n1. In our best PSI protocol, the client needs only O(n2 * log n1) memory, O(n2) symmetric cryptographic operations and O(n1) cheap hash table lookups, and the communication is O(n1 * log n1). """ 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. Trevor _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
