A Linear Reduction Method for Local Differential Privacy and Log-lift
Ni Ding, Yucheng Liu, Farhad Farokhi · 2021
This paper considers the problem of publishing data$X$while protecting the correlated sensitive information$S$. We propose a linear method to generate the sanitized data$Y$with the same alphabet$\mathcal{Y}=\mathcal{X}$that attains local differential privacy (LDP) and log-lift at the same time. It is revealed that both LDP and log-lift are inversely proportional to the statistical distance between conditional probability$P_{Y\vert S}(x\vert s)$and marginal probability$P_{Y}(x)$: the closer the two probabilities are, the more private$Y$is. Specifying$P_{Y\vert S}(x\vert s)$that linearly reduces this distance$\vert P_{Y\vert S}(x\vert s)-P_{Y}(x)\vert =(1-\alpha)\vert P_{X\vert S}(x\vert s)-P_{X}(x)\vert, \forall s, x$for some$\alpha\in(0,1]$, we study the problem of how to generate$\mathrm{Y}$from the original data$S$and$X$. The Markov randomization/sanitization scheme$P_{Y\vert X}(x\vert x^{\prime})=P_{Y\vert S,X}(x\vert s,x^{\prime})$is obtained by solving linear equations. The optimal non-Markov sanitization, the transition probability$P_{Y\vert S,X}(x\vert s,x^{\prime})$that depends on$S$,, can be determined by maximizing the data utility subject to linear equality constraints on data privacy. We compute the solution for two linear utility function: the expected distance and total variance distance. It is shown that the non-Markov randomization significantly improves data utility and the marginal probability$P_{X}(x)$remains the same after the linear sanitization method:$P_{Y}(x)=P_{X}(x),\forall x\in \mathcal{X}$.