Privacy-preserving matching of spatial datasets with protection against background knowledge

Gabriel Ghinita*, Carmen Ruiz Vicente, Ning Shang, Elisa Bertino

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
Pages3-12
Number of pages10
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010 - San Jose, CA, United States
Duration: 2 Nov 20105 Nov 2010

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Conference

Conference18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2010
Country/TerritoryUnited States
CitySan Jose, CA
Period2/11/105/11/10

Keywords

  • Location privacy
  • Privacy-preserving data linkage

Fingerprint

Dive into the research topics of 'Privacy-preserving matching of spatial datasets with protection against background knowledge'. Together they form a unique fingerprint.

Cite this