Restoring Compromised Privacy in Micro-data Disclosure

摘要

Studied in this paper is the problem of restoring compro mised privacy for micro-data disclosure with multiple dis closed views. The property of 3,-privacy is proposed, which requires that the probability of an individual to be associ ated with a sensitive value must bc bounded by γ in a possi ble 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 -y-privacy is shown to be equivalent to recursive (1-γ/γ, 2)-Diversity, which is not defined for multiple disclosed views. The problem of decid ing on γ-privacy for a set of disclosed views is proven to be #P-complete. To mitigate the high computational complex ity, the property of γ-privacy is relaxed to be satisfied with (e, 0) confidence, i.e., that the probability of disclosing a sen sitive 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 exper imental study is conducted on real-life medical data, which demonstrates that the proposed polynomial algorithms re store privacy in up to 60% of compromised disclosures.