Extending Partial Differential Private Mechanisms via Linear Programming

An (ε,δ)-DP mechanism is a mapping defined as follows. The domain of the mechanism is a finite set of objects, (also called the data points) such that a symmetric neighborhood relation over the data points is defined. The range of the mechanism at each data point is a distribution over another set. Further more, neighboring data points must be mapped to two distributions that are not far away. The parametric notion of distance of two distribution in terms of the parameters (ε,δ) in the context of privacy theory, is first introduced by Dwork and her collaborators.In this paper, we study the following problem. Given a finite set $\mathcal{D}$ of data points, the neighboring relation, the parameters ε,δ, and a partial mechanism that is defined over a subset ${\mathcal{D}^\prime } \subseteq \mathcal{D}$, is there an extension of the mechanism defined over the entire set $\mathcal{D}$ that is identical to the partial mechanism on D
^′
and also, is (ε,δ)-differential private. We show that there exists an algorithm to answer this question and it runs in time that is polynomial in the input variables. Our result generalizes a result of Medard et al. about optimum mechanism extension with respect to preferential query ordering.