Restoring Compromised Privacy in Micro-data Disclosure

摘要

Studied in this paper is the problem of restoring compromised privacy for micro-data disclosure with multiple disclosed views. The property of γ-privacy is proposed, which requires that the probability of an individual to be associated with a sensitive value must be bounded by γ in a possible table which is randomly selected from a set of tables that would lead the same disclosed answers. For the restricted case of a single disclosed view, the γ-privacy is shown to be equivalent to recursive (γ/(1-γ), 2)-Diversity, which is not defined for multiple disclosed views. The problem of deciding on γ-privacy for a set of disclosed views is proven to be #P-complete. To mitigate the high computational complexity, the property of γ-privacy is relaxed to be satisfied with (ε, θ) confidence, i.e., that the probability of disclosing a sensitive value of an individual must be bounded by γ + ε with statistical confidence θ. A Monte Carlo-based algorithm is proposed to check the relaxed property in O((λλ')~4) time for constant ε and θ, where λ is the number of tuples in the original table and λ' is the number different sensitive values in the original table. Restoring compromised privacy using additional disclosed views is studied. Heuristic polynomial time algorithms are proposed based on enumerating and checking additional disclosed views. A preliminary experimental study is conducted on real-life medical data, which demonstrates that the proposed polynomial algorithms restore privacy in up to 60% of compromised disclosures.