On Properties and Optimization of Information-theoretic Privacy Watchdog
Parastoo Sadeghi, Ni Ding, Thierry Rakotoarivelo · 2021
We study the problem of privacy preservation in data sharing, where S is a sensitive variable to be protected and X is a non-sensitive useful variable correlated with S. Variable X is randomized into variable Y, which will be shared or released according to pY |X(y|x). We measure privacy leakage by information privacy (also known as log-lift in the literature), which guarantees mutual information privacy and differential privacy (DP). Let ${\mathcal{X}}_\varepsilon ^c \subseteq {\mathcal{X}}$ contain elements in the alphabet of for which the absolute value of log-lift (abs-log-lift for short) is greater than a desired threshold ϵ. When elements $x \in {\mathcal{X}}_\varepsilon ^c$ are randomized into $y \in {\mathcal{Y}},$ we derive the best upper bound on the abs-log-lift across the resultant pairs (s, y). We then prove that this bound is achievable via an X-invariant randomization p(y|x) = R(y) for $x,y \in {\mathcal{X}}_\varepsilon ^c$. However, the utility measured by the mutual information I(X; Y) is severely damaged in imposing a strict upper bound ϵ on the abs-log-lift. To remedy this and inspired by the probabilistic (ϵ, δ)-DP, we propose a relaxed (ϵ, δ)-log-lift framework. To achieve this relaxation, we introduce a greedy algorithm which exempts some elements in ${\mathcal{X}}_\varepsilon ^c$ from randomization, as long as their abs-log-lift is bounded by ϵ with probability 1 − δ. Numerical results demonstrate efficacy of this algorithm in achieving a better privacy-utility tradeoff.