We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. We present protocols, based on the use of homomorphic encryption and balanced hashing, for both semi-honest and malicious environments. For lists of length k, we obtain O(k) communication overhead and O(k log log k) computation. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. We also consider the problem of approximating the size of the intersection, show a linear lower-bound for the communication overhead of solving this problem, and provide a suitable secure protocol. Lastly, we investigate other variants of the matching problem, including extending the protocol to the multi-party setting as well as considering the problem of approximate matching.
[ ps ] [ ps.gz ] [ pdf ] Slides: [ ppt ] [ pdf ] First paper!
Keyword Search and Oblivious Pseudorandom Functions
Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold
Theory of Cryptography Conference '05
Cambridge, MA, February 2005.
We study the problem of privacy-preserving access to a database. Particularly, we consider the problem of privacy-preserving keyword search (KS), where records in the database are accessed according to their associated keywords and where we care for the privacy of both the client and the server. We provide efficient solutions for various settings of KS, based either on specific assumptions or on general primitives (mainly oblivious transfer). Our general solutions rely on a new connection between KS and the oblivious evaluation of pseudorandom functions (OPRFs). We therefore study both the definition and construction of OPRFs and, as a corollary, give improved constructions of OPRFs that may be of independent interest.
[ ps ] [ ps.gz ] [ pdf ] Slides: [ ppt ] [ pdf ]
Efficient Private Techniques for Verifying Social Proximity
Michael J. Freedman and Antonio Nicolosi
6th International Workshop on Peer-to-Peer Systems (IPTPS '07)
Bellevue, WA, February 2007.
A variety of peer-to-peer systems use social networks to establish trust between participants. Yet the sharing of social information introduces privacy concerns. This paper proposes new privacy-preserving cryptographic protocols that enable participants to verify social proximity while exposing minimal information about the parties' social contacts. Compared to previous results, our protocols are either significantly more efficient (orders of magnitude faster than PM) or achieve stronger security properties at similar cost.