Differential privacy from axioms
This work addresses the foundational problem of privacy definitions in machine learning and data analysis, showing that DP is essentially unavoidable for any meaningful privacy notion, which is incremental as it builds on prior explorations of DP relaxations.
The paper tackles the question of whether weaker alternatives to differential privacy (DP) can still provide basic privacy guarantees while being more efficient or applicable to a broader set of tasks, and shows that any reasonable privacy measure satisfying nontrivial composition is equivalent to DP, up to polynomial factors in sample complexity.
Differential privacy (DP) is the de facto notion of privacy both in theory and in practice. However, despite its popularity, DP imposes strict requirements which guard against strong worst-case scenarios. For example, it guards against seemingly unrealistic scenarios where an attacker has full information about all but one point in the data set, and still nothing can be learned about the remaining point. While preventing such a strong attack is desirable, many works have explored whether average-case relaxations of DP are easier to satisfy [HWR13,WLF16,BF16,LWX23]. In this work, we are motivated by the question of whether alternate, weaker notions of privacy are possible: can a weakened privacy notion still guarantee some basic level of privacy, and on the other hand, achieve privacy more efficiently and/or for a substantially broader set of tasks? Our main result shows the answer is no: even in the statistical setting, any reasonable measure of privacy satisfying nontrivial composition is equivalent to DP. To prove this, we identify a core set of four axioms or desiderata: pre-processing invariance, prohibition of blatant non-privacy, strong composition, and linear scalability. Our main theorem shows that any privacy measure satisfying our axioms is equivalent to DP, up to polynomial factors in sample complexity. We complement this result by showing our axioms are minimal: removing any one of our axioms enables ill-behaved measures of privacy.