Differentially private data analysis of social networks via restricted sensitivity

We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. The definition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets. Specifically, given a query f and a hypothesis HH about the structure of a dataset D, we show generically how to transform f into a new query fHH whose global sensitivity (over all datasets including those that do not satisfy HH) matches the restricted sensitivity of the query f. Moreover, if the belief of the querier is correct (i.e., D ∈ HH) then fHH(D) = f(D). If the belief is incorrect, then fHH(D) may be inaccurate.