Differential privacy with partial knowledge
This work provides a basis for formally quantifying privacy in practical scenarios like surveys and online statistics, addressing a key limitation in differential privacy for real-world applications.
The paper tackles the problem of differential privacy's overly conservative utility due to assuming attackers with full knowledge, by proposing a framework for differential privacy with partial knowledge that addresses definitional issues for correlated data and characterizes realistic attacker models. It improves privacy analysis for counting queries and shows thresholding can provide formal guarantees even with low data entropy, linking k-anonymity to differential privacy under partial knowledge.
Differential privacy offers formal quantitative guarantees for algorithms over datasets, but it assumes attackers that know and can influence all but one record in the database. This assumption often vastly overapproximates the attackers' actual strength, resulting in unnecessarily poor utility. Recent work has made significant steps towards privacy in the presence of partial background knowledge, which can model a realistic attacker's uncertainty. Prior work, however, has definitional problems for correlated data and does not precisely characterize the underlying attacker model. We propose a practical criterion to prevent problems due to correlations, and we show how to characterize attackers with limited influence or only partial background knowledge over the dataset. We use these foundations to analyze practical scenarios: we significantly improve known results about the privacy of counting queries under partial knowledge, and we show that thresholding can provide formal guarantees against such weak attackers, even with little entropy in the data. These results allow us to draw novel links between k-anonymity and differential privacy under partial knowledge. Finally, we prove composition results on differential privacy with partial knowledge, which quantifies the privacy leakage of complex mechanisms. Our work provides a basis for formally quantifying the privacy of many widely-used mechanisms, e.g. publishing the result of surveys, elections or referendums, and releasing usage statistics of online services.