Reasoning about privacy using axioms
Bing-Rong Lin, Daniel Kifer · 2012
In statistical privacy, privacy definitions are contracts that guide the behavior of algorithms that take in sensitive data and produce sanitized data. Historically, data privacy breaches have been the result of fundamental misunderstandings about what a particular privacy definition guarantees. Privacy definitions are often analyzed using a hit-or-miss approach: a specific attack strategy is evaluated to determine if a specific type of information can be inferred. If the attack works, the privacy definition is known to be too weak. If it doesn't work, little information is gained. Furthermore, these strategies will not identify cases where a privacy definition protects unnecessary pieces of information. A systematic analysis of privacy definitions is a long-standing open problem. In this paper, we present initial steps towards a solution. Using privacy axioms, we identify two mathematical objects that are associated with privacy definitions - the consistent closure and the row cone (which is constructed from the consistent closure). The row cone is a geometric object which neatly encapsulates Bayesian guarantees provided by a privacy definition. We apply these ideas to the study of randomized response to show that it provides unnecessarily strong protections on the parity of a dataset.