The Boundary Between Privacy and Utility in Data Anonymization

Simple item page
dc.creatorRastogi, Vibhor
dc.creatorSuciu, Dan
dc.creatorHong, Sungho
dc.date2006-12-21
dc.date.accessioned2026-07-07T07:36:33Z
dc.date.available2026-07-07T07:36:33Z
dc.descriptionWe consider the privacy problem in data publishing: given a relation I containing sensitive information 'anonymize' it to obtain a view V such that, on one hand attackers cannot learn any sensitive information from V, and on the other hand legitimate users can use V to compute useful statistics on I. These are conflicting goals. We use a definition of privacy that is derived from existing ones in the literature, which relates the a priori probability of a given tuple t, Pr(t), with the a posteriori probability, Pr(t | V), and propose a novel and quite practical definition for utility. Our main result is the following. Denoting n the size of I and m the size of the domain from which I was drawn (i.e. n < m) then: when the a priori probability is Pr(t) = Omega(n/sqrt(m)) for some t, there exists no useful anonymization algorithm, while when Pr(t) = O(n/m) for all tuples t, then we give a concrete anonymization algorithm that is both private and useful. Our algorithm is quite different from the k-anonymization algorithm studied intensively in the literature, and is based on random deletions and insertions to I.
dc.identifierhttps://arxiv.org/abs/cs/0612103
dc.identifierhttp://arxiv.org/abs/cs/0612103
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/120462
dc.subjectDatabases
dc.titleThe Boundary Between Privacy and Utility in Data Anonymization
dc.typetext

Files

Collections

arXiv