A Linear Reduction Method for Local Differential Privacy and Log-lift

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}$ .