Skip to Main content Skip to Navigation
New interface
Journal articles

ρ-uncertainty: Inference-Proof Transaction Anonymization

Jianneng Cao 1, * Panagiotis Karras 1 Chedy Raïssi 2 Kian-Lee Tan 1 
* Corresponding author
2 ORPAILLEUR - Knowledge representation, reasonning
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The publication of transaction data, such as market basket data, medical records, and query logs, serves the public benefit. Mining such data allows for the derivation of association rules that connect certain items to others with measurable confidence. Still, this type of data analysis poses a privacy threat; an adversary having partial information on a person's behavior may confidently associate that person to an item deemed to be sensitive. Ideally, an anonymization of such data should lead to an inference-proof version that prevents the association of individuals to sensitive items, while otherwise allowing for truthful associations to be derived. Original approaches to this problem were based on value perturbation, damaging data integrity. Recently, value generalization has been proposed as an alternative; still, approaches based on it have assumed either that all items are equally sensitive, or that some are sensitive and can be known to an adversary only by association, while others are non-sensitive and can be known directly. Yet in reality there is a distinction between sensitive and non-sensitive items, but an adversary may possess information on any of them. Most critically, no antecedent method aims at a clear inference-proof privacy guarantee. In this paper, we propose 휌-uncertainty, the first, to our knowledge, privacy concept that inherently safeguards against sensitive associations without constraining the nature of an adversary's knowledge and without falsifying data. The problem of achieving 휌-uncertainty with low information loss is challenging because it is natural. A trivial solution is to suppress all sensitive items. We develop more sophisticated schemes. In a broad experimental study, we show that the problem is solved non-trivially by a technique that combines generalization and suppression, which also achieves favorable results compared to a baseline perturbation-based scheme.
Document type :
Journal articles
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Chedy Raïssi Connect in order to contact the contributor
Submitted on : Monday, July 25, 2011 - 12:15:47 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:45 PM
Long-term archiving on: : Wednesday, October 26, 2011 - 2:21:33 AM


Publisher files allowed on an open archive


  • HAL Id : inria-00610934, version 1



Jianneng Cao, Panagiotis Karras, Chedy Raïssi, Kian-Lee Tan. ρ-uncertainty: Inference-Proof Transaction Anonymization. Proceedings of the VLDB Endowment (PVLDB), 2010, 3 (1), pp.1033-1044. ⟨inria-00610934⟩



Record views


Files downloads