TY - CHAP
T1 - Efficient private matching and set intersection
AU - Freedman, Michael J.
AU - Nissim, Kobbi
AU - Pinkas, Benny
PY - 2004
Y1 - 2004
N2 - 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 ln ln 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.
AB - 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 ln ln 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.
UR - http://www.scopus.com/inward/record.url?scp=35048820609&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048820609&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-24676-3_1
DO - 10.1007/978-3-540-24676-3_1
M3 - Chapter
AN - SCOPUS:35048820609
SN - 3540219358
SN - 9783540219354
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 19
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Cachin, Christian
A2 - Camenisch, Jan
PB - Springer Verlag
ER -