Generalizing data to provide anonymity when disclosing information (abstract)

By Pierangela Samarati, Latanya Sweeney. 1998

The proliferation of information on the Internet and access to fast computers with large storage capacities has increased tho volume of information collected and disseminated about individuals, The existence of these other data sources makes it much easier to re-identify individuals whose private information is released in data believed to be anonymous. At the same time, increasing demands are made on organizations to release individualized data rather than aggregate statistical information. Even when explicit identifiers, such as name and phone number, are removed or encrypted when releasing individualized data, other characteristic data may still uniquely combine into a quasi-identifier, which can allow data recipients to re-identify individuals to whom the data refer. In this paper, we provide a technique for releasing information such that the ability to link the released data to other information is limited in an attempt to protect the idcntitics of individuals. We use generalization, by which stored values can be replaced with semantically consistent but less precise alternatives, and k-anonymity. A table provides k-anonymity when each combination of values that is associated with a quasi-identifier occurs k or more times, making it difficult to link the quasi-identifier to other data with confidence. We introduce the notions of generalized table and of minimal generalization of a table with respect to a k-anonymity requirement. As an optimization problcm, the objective is to minimally distort the data while providing adequate protection. We describe an algorithm that, given a table, efficiently computes a preferred minimal gcnoralization to provide anonymity.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prochlo: Strong Privacy for Analytics in the Crowd (2017, background): “For example, the well-known property of k-anonymity prevents direct release of information about subgroups with fewer than k individuals [65, 66].”
Privacy integrated queries: an extensible platform for privacy-preserving data analysis (2009, background): “Unfortunately, sanitization is neither easy to do, nor even to define; research in the area has yet to stabilize on robust definitions that come without known vulnerabilities [7, 8, 9].”
Privacy integrated queries (2010, background): “Unfortunately, sanitization is neither easy to do, nor even to define; research in the area has yet to stabilize on robust definitions that come without known vulnerabilities [ 7 , 8, 9]. Furthermore, these approaches intentionally contort the data before release, requiring the analyst to understand”
On the complexity of optimal K-anonymity (2004, methodology): “[9] L. Sweeney. k-anonymity: a model for protecting privacy.”
K-Automorphism: A General Framework For Privacy Preserving Network Publication (2009, background): “Obviously, if G is a k -automorphic network, for any vertex v in G , we cannot distinguish v from its k − 1 symmetric vertices based on any structural information.”
δ-Presence without Complete World Knowledge (2010, background): “Ç”
An Ad Omnia Approach to Defining and Achieving Private Data Analysis (2007, unknown): “Sweeney proposed an antidote: k-anonymity [38] [39] [41] [42].”
k -Anonymous Data Mining: A Survey (2008, background): “been married M [40-100) 17 been married F [1-40) 2 been married F [40-100) 9 never married M [40-100) 26”
Protecting privacy when mining and sharing user data (2012, background): “The privacy protection of k-anonymity [161, 175] is to guarantee that every set of quasi-identifiers appears in at least k records in the data set, or equivalently, that any particular individual’s data is indistinguishable from data of at least k 1 other individuals with respect to the quasi-identi”
Technical Privacy Metrics (2015, methodology): “Several algorithms exist that transform a given database to make it k -anonymous by suppression or generalization [Samarati and Sweeney 1998].”