TY - GEN
T1 - Large-scale multi-party counting set intersection using a space efficient global synopsis
AU - Karapiperis, Dimitrios
AU - Vatsalan, Dinusha
AU - Verykios, Vassilios S.
AU - Christen, Peter
N1 - Publisher Copyright:
© 2015, Springer International Publishing Switzerland, All rights Reserved.
PY - 2015
Y1 - 2015
N2 - Privacy-preserving set intersection (PPSI) of very large data sets is increasingly being required in many real application areas including health-care, national security, and law enforcement. Various techniques have been developed to address this problem, where the majority of them rely on computationally expensive cryptographic techniques. Moreover, conventional data structures cannot be used efficiently for providing count estimates of the elements of the intersection of very large data sets. We consider the problem of efficient PPSI by integrating sets from multiple (three or more) sources in order to create a global synopsis which is the result of the intersection of efficient data structures, known as Count-Min sketches. This global synopsis furthermore provides count estimates of the intersected elements. We propose two protocols for the creation of this global synopsis which are based on homomorphic computations, a secure distributed summation scheme, and a symmetric noise addition technique. Experiments conducted on large synthetic and real data sets show the efficiency and accuracy of our protocols, while at the same time privacy under the Honest-but-Curious model is preserved.
AB - Privacy-preserving set intersection (PPSI) of very large data sets is increasingly being required in many real application areas including health-care, national security, and law enforcement. Various techniques have been developed to address this problem, where the majority of them rely on computationally expensive cryptographic techniques. Moreover, conventional data structures cannot be used efficiently for providing count estimates of the elements of the intersection of very large data sets. We consider the problem of efficient PPSI by integrating sets from multiple (three or more) sources in order to create a global synopsis which is the result of the intersection of efficient data structures, known as Count-Min sketches. This global synopsis furthermore provides count estimates of the intersected elements. We propose two protocols for the creation of this global synopsis which are based on homomorphic computations, a secure distributed summation scheme, and a symmetric noise addition technique. Experiments conducted on large synthetic and real data sets show the efficiency and accuracy of our protocols, while at the same time privacy under the Honest-but-Curious model is preserved.
UR - http://www.scopus.com/inward/record.url?scp=84942570977&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18123-3_20
DO - 10.1007/978-3-319-18123-3_20
M3 - Conference contribution
SN - 9783319181226
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 329
EP - 345
BT - Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II
A2 - Cheema, Muhammad Aamir
A2 - Renz, Matthias
A2 - Shahabi, Cyrus
A2 - Zhou, Xiaofang
PB - Springer Verlag
T2 - 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Y2 - 20 April 2015 through 23 April 2015
ER -