Privacy-Preserving Matching of Spatial Datasets with Protection against Background Knowledge

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 spaceembedding
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 L1,
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.