The massive collection of personal data by personalization systems has
rendered the preservation of privacy of individuals more and more difficult.
Most of the proposed approaches to preserve privacy in personalization systems
usually address this issue uniformly across users, thus ignoring the fact that
users have different privacy attitudes and expectations (even among their own
personal data). In this paper, we propose to account for this non-uniformity of
privacy expectations by introducing the concept of heterogeneous differential
privacy. This notion captures both the variation of privacy expectations among
users as well as across different pieces of information related to the same
user. We also describe an explicit mechanism achieving heterogeneous
differential privacy, which is a modification of the Laplacian mechanism by
Dwork, McSherry, Nissim, and Smith. In a nutshell, this mechanism achieves
heterogeneous differential privacy by manipulating the sensitivity of the
function using a linear transformation on the input domain. Finally, we
evaluate on real datasets the impact of the proposed mechanism with respect to
a semantic clustering task. The results of our experiments demonstrate that
heterogeneous differential privacy can account for different privacy attitudes
while sustaining a good level of utility as measured by the recall for the
semantic clustering task.

本文提出一种异构的差分隐私概念，旨在充分考虑用户之间的隐私态度和期望差异，结合 Laplacian 机制实现个性化系统中的隐私保护，并在真实数据集上实验证明该方法能够在保障隐私同时保持良好的语义聚类结果。

异构差分隐私

Heterogeneous Differential Privacy

We derive the optimal $\epsilon$-differentially private mechanism for single
real-valued query function under a very general utility-maximization (or
cost-minimization) framework. The class of noise probability distributions in
the optimal mechanism has {\em staircase-shaped} probability density functions
which are symmetric (around the origin), monotonically decreasing and
geometrically decaying. The staircase mechanism can be viewed as a {\em
geometric mixture of uniform probability distributions}, providing a simple
algorithmic description for the mechanism. Furthermore, the staircase mechanism
naturally generalizes to discrete query output settings as well as more
abstract settings. We explicitly derive the optimal noise probability
distributions with minimum expectation of noise amplitude and power. Comparing
the optimal performances with those of the Laplacian mechanism, we show that in
the high privacy regime ($\epsilon$ is small), Laplacian mechanism is
asymptotically optimal as $\epsilon \to 0$; in the low privacy regime
($\epsilon$ is large), the minimum expectation of noise amplitude and minimum
noise power are $\Theta(\Delta e^{-\frac{\epsilon}{2}})$ and $\Theta(\Delta^2
e^{-\frac{2\epsilon}{3}})$ as $\epsilon \to +\infty$, while the expectation of
noise amplitude and power using the Laplacian mechanism are
$\frac{\Delta}{\epsilon}$ and $\frac{2\Delta^2}{\epsilon^2}$, where $\Delta$ is
the sensitivity of the query function. We conclude that the gains are more
pronounced in the low privacy regime.

本文提出了单一实值查询函数的最优 ε- 差分隐私机制，其噪声概率分布类具有楼梯形状、对称性、单调递减和几何衰减，可以被视为均匀概率分布的几何混合，并将此机制自然地推广到了离散查询输出环境和更抽象的环境中。通过将最优性能与拉普拉斯机制的性能进行比较，我们得出结论，当 ε 趋近于 0 时，拉普拉斯机制是渐近最优的；而在 ε 趋近于 +∞时，最小噪声振幅和最小噪声功率分别为 Θ(Δe^-ε/2) 和 Θ(Δ^2 e^-2ε/3)，而拉普拉斯机制的噪声振幅和功率期望分别为 Δ/ε 和 2Δ^2/ε^2，在低隐私保护级别下获得更明显的收益。