d_X-Private Mechanisms for Linear Queries
share
Differential Privacy is one of the strongest privacy guarantees, which allows the release of useful information about any sensitive dataset. However, it provides the same level of protection for all elements in the data universe. In this paper, we consider d_X-privacy, an instantiation of the privacy notion introduced in chatzikokolakis2013broadening, which allows specifying a separate privacy budget for each pair of elements in the data universe. We describe a systematic procedure to tailor any existing differentially private mechanism into a d_X-private variant for the case of linear queries. For the resulting d_X-private mechanisms, we provide theoretical guarantees on the trade-off between utility and privacy, and show that they always outperform their vanilla counterpart. We demonstrate the effectiveness of our procedure, by evaluating the proposed d_X-private Laplace mechanism on both synthetic and real datasets using a set of randomly generated linear queries.
READ FULL TEXT