Concerns on location privacy frequently arise with the rapid development of
GPS enabled devices and location-based applications. While spatial
transformation techniques such as location perturbation or generalization have
been studied extensively, most techniques rely on syntactic privacy models
without rigorous privacy guarantee. Many of them only consider static scenarios
or perturb the location at single timestamps without considering temporal
correlations of a moving user's locations, and hence are vulnerable to various
inference attacks. While differential privacy has been accepted as a standard
for privacy protection, applying differential privacy in location based
applications presents new challenges, as the protection needs to be enforced on
the fly for a single user and needs to incorporate temporal correlations
between a user's locations.
In this paper, we propose a systematic solution to preserve location privacy
with rigorous privacy guarantee. First, we propose a new definition,
"$\delta$-location set" based differential privacy, to account for the temporal
correlations in location data. Second, we show that the well known
$\ell_1$-norm sensitivity fails to capture the geometric sensitivity in
multidimensional space and propose a new notion, sensitivity hull, based on
which the error of differential privacy is bounded. Third, to obtain the
optimal utility we present a planar isotropic mechanism (PIM) for location
perturbation, which is the first mechanism achieving the lower bound of
differential privacy. Experiments on real-world datasets also demonstrate that
PIM significantly outperforms baseline approaches in data utility.

该论文提出了一种系统性解决方案以保护位置隐私，通过引入 “delta-location set” 基于差分隐私的定义来考虑位置数据中的时间相关性，提出了一个新的敏感度计算概念 —— 精度壳，为位置扰动提出了一个平面各向同性机制， 经实验验证，在数据的效用方面优于基线方法。