Evaluating privacy threats in released database views by symmetric indistinguishability

A privacy violation occurs when the association between an individual identity and data considered private by that individual is obtained by an unauthorized party. Uncertainty and indistinguishability are two independent aspects that characterize the degree of this association being revealed. Indistinguishability refers to the property that the attacker cannot see the difference among a group of individuals, while uncertainty refers to the property that the attacker cannot tell which private value, among a group of values, an individual actually has. This paper investigates the notion of indistinguishability as a general form of anonymity, applicable, for example, not only to generalized private tables, but to relational views and to sets of views obtained by multiple queries over a private database table. It is shown how indistinguishability is highly influenced by certain symmetries among individuals, in the released data, with respect to their private values. The paper provides both theoretical results and practical algorithms for checking if a specific set of views over a private table provide sufficient indistinguishability.