TY - GEN
T1 - Privacy-preserving matching of spatial datasets with protection against background knowledge
AU - Ghinita, Gabriel
AU - Vicente, Carmen Ruiz
AU - Shang, Ning
AU - Bertino, Elisa
PY - 2010
Y1 - 2010
N2 - Private matching (or join) of spatial datasets is crucial for applications where distinct parties wish to share information about nearby geo-tagged data items. To protect each party's data, only joining pairs of points should be revealed, and no additional information about non-matching items should be disclosed. Previous research efforts focused on private matching for relational data, and rely either on space-embedding or on SMC techniques. Space-embedding transforms data points to hide their exact attribute values before matching is performed, whereas SMC protocols simulate complex digital circuits that evaluate the matching condition without revealing anything else other than the matching outcome. However, existing solutions have at least one of the following drawbacks: (i) they fail to protect against adversaries with background knowledge on data distribution, (ii) they compromise privacy by returning large amounts of false positives and (iii) they rely on complex and expensive SMC protocols. In this paper, we introduce a novel geometric transformation to perform private matching on spatial datasets. Our method is efficient and it is not vulnerable to background knowledge attacks. We consider two distance evaluation metrics in the transformed space, namely L2 and L ∞, and show how the metric used can control the trade-off between privacy and the amount of returned false positives. We provide an extensive experimental evaluation to validate the precision and efficiency of our approach.
AB - Private matching (or join) of spatial datasets is crucial for applications where distinct parties wish to share information about nearby geo-tagged data items. To protect each party's data, only joining pairs of points should be revealed, and no additional information about non-matching items should be disclosed. Previous research efforts focused on private matching for relational data, and rely either on space-embedding or on SMC techniques. Space-embedding transforms data points to hide their exact attribute values before matching is performed, whereas SMC protocols simulate complex digital circuits that evaluate the matching condition without revealing anything else other than the matching outcome. However, existing solutions have at least one of the following drawbacks: (i) they fail to protect against adversaries with background knowledge on data distribution, (ii) they compromise privacy by returning large amounts of false positives and (iii) they rely on complex and expensive SMC protocols. In this paper, we introduce a novel geometric transformation to perform private matching on spatial datasets. Our method is efficient and it is not vulnerable to background knowledge attacks. We consider two distance evaluation metrics in the transformed space, namely L2 and L ∞, and show how the metric used can control the trade-off between privacy and the amount of returned false positives. We provide an extensive experimental evaluation to validate the precision and efficiency of our approach.
KW - Location privacy
KW - Privacy-preserving data linkage
UR - http://www.scopus.com/inward/record.url?scp=78650588629&partnerID=8YFLogxK
U2 - 10.1145/1869790.1869795
DO - 10.1145/1869790.1869795
M3 - Conference contribution
AN - SCOPUS:78650588629
SN - 9781450304283
T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
SP - 3
EP - 12
BT - 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
T2 - 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
Y2 - 2 November 2010 through 5 November 2010
ER -