Kantorovich Mechanism for Pufferfish Privacy

Pufferfish privacy achieves $\epsilon$-indistinguishability over a set of secret pairs in the disclosed dataset. This paper studies how to attain pufferfish privacy by the exponential mechanism, an additive noise scheme that generalizes Gaussian and Laplace noise. A sufficient condition is derived showing that pufferfish privacy is attained by calibrating noise to the sensitivity of the Kantorovich optimal transport plan. Such a plan can be directly computed by using the data statistics conditioned on the secret, the prior knowledge about the system. It is shown that Gaussian noise provides better data utility than Laplace noise when the privacy budget $\epsilon$ is small. The sufficient condition is then relaxed to reduce the noise power. Experimental results show that the relaxed sufficient condition improves data utility of the pufferfish private data regulation schemes.