Masking and Re-identification Methods for Public-Use Microdata: Overview and Research Problems
---
paper_title: Inference Control in Statistical Databases

paper_content:

PCT No. PCT/EP95/04271 Sec. 371 Date Jun. 2, 1998 Sec. 102(e) Date Jun. 2, 1998 PCT Filed Oct. 27, 1995 PCT Pub. No. WO97/16265 PCT Pub. Date May 9, 1997During a rinsing stage a first quantity of water is accumulated in a buffer reservoir and the tank is rinsed. During a washing stage a second quantity of water is accumulated and the milk tank is washed. A first period of time used for accumulating the first quantity is measured. A second period of time is determined from the measured first period of time and either the first quantity and the second quantity or the ratio between the first quantity and the second quantity. During the washing stage water is supplied during the second period of time. A flexible and reliable method of dosing the second quantity of water essentially independently of the prevailing water pressure is obtained, which does not require a correspondingly large reservoir or any instruments specially provided for measuring the second quantity of water.
---
paper_title: Security of statistical databases: multidimensional transformation

paper_content:

Statistical evaluation of databases which contain personal records may entail risks for the confidentiality of the individual records. The risk has increased with the availability of flexible interactive evaluation programs which permit the use of trackers, the most dangerous class of snooping tools known. A class of trackers, called union trackers, is described. They permit reconstruction of the entire database without supplementary knowledge and include the general tracker recently described as a special case. For many real statistical databases the overwhelming majority of definable sets of records will form trackers. For such databases a random search for a tracker is likely to succeed rapidly. Individual trackers are redefined and counted and their cardinalities are investigated. If there are n records in the database, then most individual trackers employ innocent cardinalities near n /3, making them difficult to detect. Disclosure with trackers usually requires little effort per retrieved data element.
---
paper_title: A Bayesian Approach to Data Disclosure: Optimal Intruder Behavior for Continuous Data

paper_content:

There has been a longstanding government interest and concern in the United States and elsewhere over the confidentiality of statistical data, especially as gathered in sample surveys and censuses. For example, the U.S. Bureau of the Census operates under Title 13 of the U.S. Code, virtually from its inception in 1929. Such legal guarantees of confidentiality are not only a reflection of the public concerns regarding disclosure but also of the agencies’ desire for high quality data. Even in the absence of legal restrictions on access to data, statistical agencies and survey researchers have always been concerned about the need to preserve the confidentiality of respondents in order to ensure the quality of the data provided, and these concerns have been heightened by the decline in response rates for censuses and surveys over the past two decades (e.g., see Panel on Privacy and Confidentiality as Factors in Survey Response 1979; Fienberg 1993‐1994). At the same time government agencies have an obligation to report their data widely and thus they recognize the need for some balance between strict confidentiality (however it is to be interpreted) and the benefits derived from the release of statistical information. To In this article we develop an approach to data disclosure in survey settings by adopting a probabilistic definition of disclosure due to Dalenius. Our approach is based on the principle that a data collection agency must consider disclosure from the perspective of an intruder in order to efficiently evaluate data disclosure limitation procedures. The probabilistic definition and our attempt to study optimal intruder behavior lead naturally to a Bayesian formulation. We apply the methods in a small-scale simulation study using data adapted from an actual survey conducted by the Institute for Social Research at York University.
---
paper_title: Practical data-swapping: the first steps

paper_content:

The problem of statistical database confidentiality in releasing microdata is addressed through the use of approximate data-swapping. Here, a portion of the microdata is replaced with a database that has been selected with approximately the same statistics. The result guarantees the confidentiality of the original data, while providing microdata with accurate statistics. Methods for achieving such transformations are considered and analyzed through simulation.
---
paper_title: Releasing Multiply Imputed, Synthetic Public-Use Microdata: An Illustration and Empirical

paper_content:

The paper presents an illustration and empirical study of releasing multiply imputed, fully synthetic public use microdata. Simulations based on data from the US Current Population Survey are used to evaluate the potential validity of inferences based on fully synthetic data for a variety of descriptive and analytic estimands, to assess the degree of protection of confidentiality that is afforded by fully synthetic data and to illustrate the specification of synthetic data imputation models. Benefits and limitations of releasing fully synthetic data sets are discussed. Copyright 2005 Royal Statistical Society.
---
paper_title: Practical data-oriented microaggregation for statistical disclosure control

paper_content:

Microaggregation is a statistical disclosure control technique for microdata disseminated in statistical databases. Raw microdata (i.e., individual records or data vectors) are grouped into small aggregates prior to publication. Each aggregate should contain at least k data vectors to prevent disclosure of individual information, where k is a constant value preset by the data protector. No exact polynomial algorithms are known to date to microaggregate optimally, i.e., with minimal variability loss. Methods in the literature rank data and partition them into groups of fixed-size; in the multivariate case, ranking is performed by projecting data vectors onto a single axis. In this paper, candidate optimal solutions to the multivariate and univariate microaggregation problems are characterized. In the univariate case, two heuristics based on hierarchical clustering and genetic algorithms are introduced which are data-oriented in that they try to preserve natural data aggregates. In the multivariate case, fixed-size and hierarchical clustering microaggregation algorithms are presented which do not require data to be projected onto a single dimension; such methods clearly reduce variability loss as compared to conventional multivariate microaggregation on projected data.
---
paper_title: Maximum entropy simulation for microdata protection

paper_content:

The paper proposes a new disclosure limitation procedure based on simulation. The key feature of the proposal is to protect actual microdata by drawing artificial units from a probability model, that is estimated from the observed data. Such a model is designed to maintain selected characteristics of the empirical distribution, thus providing a partial representation of the latter. The characteristics we focus on are the expected values of a set of functionss these are constrained to be equal to their corresponding sample averagess the simulated data, then, reproduce on average the sample characteristics. If the set of constraints covers the parameters of interest of a user, information loss is controlled for, while, as the model does not preserve individual values, re-identification attempts are impaired-synthetic individuals correspond to actual respondents with very low probability. ::: ::: Disclosure is mainly discussed from the viewpoint of record re-identification. According to this definition, as the pledge for confidentiality only involves the actual respondents, release of synthetic units should in principle rule out the concern for confidentiality. ::: ::: The simulation model is built on the Italian sample from the Community Innovation Survey (CIS). The approach can be applied in more generality, and especially suits quantitative traits. The model has a semi-parametric component, based on the maximum entropy principle, and, here, a parametric component, based on regression. The maximum entropy principle is exploited to match data traitss moreover, entropy measures uncertainty of a distribution: its maximisation leads to a distribution which is consistent with the given information but is maximally noncommittal with regard to missing information. ::: ::: Application results reveal that the fixed characteristics are sustained, and other features such as marginal distributions are well represented. Model specification is clearly a major points related issues are selection of characteristics, goodness of fit and strength of dependence relations.
---
paper_title: A computational algorithm for handling the special uniques problem

paper_content:

Many organizations require detailed individual-level information, much of which has been collected under guarantees of confidentiality. However, simple anonymization procedures, i.e. removing names and addresses, are insufficient for this to be ensured. The records belonging to certain individuals have a high probability of being identified (as their contents, or attributes, are unusual) and therefore have the potential to be recognized spontaneously - such records are referred to as special uniques. Consider, for example, a sixteen-year-old widow in a population survey. Confidentiality of a given dataset cannot be enabled until all special unique records are identified and either disguised or removed. However, to the knowledge of the authors, no exhaustive automated analysis of this nature has been conducted due to the demanding levels of computation and data storage that are required. This paper introduces a new algorithm that locates 'risky' records in discrete data by first identifying all unique attribute sets (up to a user-specified maximum size) and secondly by grading the 'risk' of each record by considering the number and distribution of unique attribute sets within each record. Empirical tests indicate that the algorithm is highly effective at picking out 'risky' records from large samples of data.
---
paper_title: A General Additive Data Perturbation Method for Database Security

paper_content:

The security of organizational databases has received considerable attention in the literature in recent years. This can be attributed to a simultaneous increase in the amount of data being stored in databases, the analysis of such data, and the desire to protect confidential data. Data perturbation methods are often used to protect confidential, numerical data from unauthorized queries while providing maximum access and accurate information to legitimate queries. To provide accurate information, it is desirable that perturbation does not result in a change in relationships between attributes. In the presence of nonconfidential attributes, existing methods will result in such a change. This study describes a new method (General Additive Data Perturbation) that does not change relationships between attributes. All existing methods of additive data perturbation are shown to be special cases of this method. When the database has a multivariate normal distribution, the new method provides maximum security and minimum bias. For nonnormal databases, the new method provides better security and bias performance than the multiplicative data perturbation method.
---
paper_title: An Improved Security Requirement for Data Perturbation with Implications for E-Commerce

paper_content:

With the rapid increase in the ability to store and analyze large amounts of data, organizations are gathering extensive data regarding their customers, vendors, and other entities. There has been a concurrent increase in the demand for preserving the privacy of confidential data that may be collected. The rapid growth of e-commerce has also increased calls for maintaining privacy and confidentiality of data. For numerical data, data perturbation methods offer an easy yet effective solution to the dilemma of providing access to legitimate users while protecting the data from snoopers (legitimate users who perform illegitimate analysis). In this study, we define a new security requirement that achieves the objective of providing access to legitimate users without an increase in the ability of a snooper to predict confidential information. We also derive the specifications under which perturbation methods can achieve this objective. Numerical examples are provided to show that the use of the new specification achieves the objective of no additional information to the snooper. Implications of the new specification for e-commerce are discussed.
---
paper_title: Releasing Multiply Imputed, Synthetic Public-Use Microdata: An Illustration and Empirical

paper_content:

The paper presents an illustration and empirical study of releasing multiply imputed, fully synthetic public use microdata. Simulations based on data from the US Current Population Survey are used to evaluate the potential validity of inferences based on fully synthetic data for a variety of descriptive and analytic estimands, to assess the degree of protection of confidentiality that is afforded by fully synthetic data and to illustrate the specification of synthetic data imputation models. Benefits and limitations of releasing fully synthetic data sets are discussed. Copyright 2005 Royal Statistical Society.
---
paper_title: LHS-Based Hybrid Microdata vs Rank Swapping and Microaggregation for Numeric Microdata Protection

paper_content:

In previous work by Domingo-Ferrer et al., rank swapping and multivariate microaggregation has been identified as well-performing masking methods for microdata protection. Recently, Dandekar et al. proposed using synthetic microdata, as an option, in place of original data by using Latin hypercube sampling (LHS) technique. The LHS method focuses on mimicking univariate as well as multivariate statistical characteristics of original data. The LHS-based synthetic data does not allow one to one comparison with original data. This prevents estimating the overall information loss by using current measures. In this paper we utilize unique features of LHS method to create hybrid data sets and evaluate their performance relative to rank swapping and multivariate microaggregation using generalized information loss and disclosure risk measures.
---
paper_title: Maximum entropy simulation for microdata protection

paper_content:

The paper proposes a new disclosure limitation procedure based on simulation. The key feature of the proposal is to protect actual microdata by drawing artificial units from a probability model, that is estimated from the observed data. Such a model is designed to maintain selected characteristics of the empirical distribution, thus providing a partial representation of the latter. The characteristics we focus on are the expected values of a set of functionss these are constrained to be equal to their corresponding sample averagess the simulated data, then, reproduce on average the sample characteristics. If the set of constraints covers the parameters of interest of a user, information loss is controlled for, while, as the model does not preserve individual values, re-identification attempts are impaired-synthetic individuals correspond to actual respondents with very low probability. ::: ::: Disclosure is mainly discussed from the viewpoint of record re-identification. According to this definition, as the pledge for confidentiality only involves the actual respondents, release of synthetic units should in principle rule out the concern for confidentiality. ::: ::: The simulation model is built on the Italian sample from the Community Innovation Survey (CIS). The approach can be applied in more generality, and especially suits quantitative traits. The model has a semi-parametric component, based on the maximum entropy principle, and, here, a parametric component, based on regression. The maximum entropy principle is exploited to match data traitss moreover, entropy measures uncertainty of a distribution: its maximisation leads to a distribution which is consistent with the given information but is maximally noncommittal with regard to missing information. ::: ::: Application results reveal that the fixed characteristics are sustained, and other features such as marginal distributions are well represented. Model specification is clearly a major points related issues are selection of characteristics, goodness of fit and strength of dependence relations.
---
paper_title: Uniqueness and disclosure limitation for categorical data

paper_content:

This invention relates to a vehicle sun roof, preferably transparent or translucent such as glass or plastic, which contains the following characteristics:
---
paper_title: Modelling user uncertainty for disclosure risk and data utility

paper_content:

In this paper we show how a simple model that captures user uncertainty can be used to define suitable measures of disclosure risk and data utility. The model generalizes previous results of Duncan and Lambert. We present several examples to illustrate how the new measures can be used to implement existing optimality criteria for the choice of the best form of data release.
---
paper_title: A computational algorithm for handling the special uniques problem

paper_content:

Many organizations require detailed individual-level information, much of which has been collected under guarantees of confidentiality. However, simple anonymization procedures, i.e. removing names and addresses, are insufficient for this to be ensured. The records belonging to certain individuals have a high probability of being identified (as their contents, or attributes, are unusual) and therefore have the potential to be recognized spontaneously - such records are referred to as special uniques. Consider, for example, a sixteen-year-old widow in a population survey. Confidentiality of a given dataset cannot be enabled until all special unique records are identified and either disguised or removed. However, to the knowledge of the authors, no exhaustive automated analysis of this nature has been conducted due to the demanding levels of computation and data storage that are required. This paper introduces a new algorithm that locates 'risky' records in discrete data by first identifying all unique attribute sets (up to a user-specified maximum size) and secondly by grading the 'risk' of each record by considering the number and distribution of unique attribute sets within each record. Empirical tests indicate that the algorithm is highly effective at picking out 'risky' records from large samples of data.
---
paper_title: Disclosure Control of Microdata

paper_content:

Abstract National statistical offices meet an increasing demand for the dissemination of microdata. This trend can be at variance with the care taken not to disclose data about individuals. Therefore, the risk of disclosure of each microdata set to be released should be assessed. If this risk is too high, measures have to be taken to protect the data set. This article describes the disclosure problem, and explains why it is a real problem. Using the concept of uniqueness, some theory is developed that can help establish the risk of identification. It turns out that useful microdata sets can only be released if some of the disclosure risks are dealt with by legal arrangements, rather than by restrictions on the data to be released.
---
paper_title: The use of regression methodology for the compromise of confidential information in statistical databases

paper_content:

A regression methodology based technique can be used to compromise confidentiality in a statistical database. This holds true even when the DBMS prevents application of regression methodology to the database. Existing inference controls, including cell restriction, perturbation, and table restriction approaches, are shown to be generally ineffective against this compromise technique. The effect of incomplete supplemental knowledge on the regression methodology based compromise technique is examined. Finally, some potential complicators of this disclosure scheme are introduced.
---
paper_title: A Bayesian Hierarchical Model Approach to Risk Estimation in Statistical Disclosure Limitation

paper_content:

When microdata files for research are released, it is possible that external users may attempt to breach confidentiality. For this reason most National Statistical Institutes apply some form of disclosure risk assessment and data protection. Risk assessment first requires a measure of disclosure risk to be defined. In this paper we build on previous work by [BF98] to define a Bayesian hierarchical model for risk estimation. We follow a superpopulation approach similar to [BKP90] and [Rin03]. For each combination of values of the key variables we derive the posterior distribution of the population frequency given the observed sample frequency. Knowledge of this posterior distribution enables us to obtain suitable summaries that can be used to estimate the risk of disclosure. One such summary is the mean of the reciprocal of the population frequency or Benedetti-Franconi risk, but we also investigate others such as the mode. We apply our approach to an artificial sample of the Italian 1991 Census data, drawn by means of a widely used sampling scheme. We report on results of this application and document the computational difficulties that we encountered. The risk estimates that we obtain are sensible, but suggest possible improvements and modifications to our methodology. We discuss these together with potential alternative strategies.
---
paper_title: Achieving k-Anonymity Privacy Protection Using Generalization and Suppression

paper_content:

Often a data holder, such as a hospital or bank, needs to share person-specific records in such a way that the identities of the individuals who are the subjects of the data cannot be determined. One way to achieve this is to have the released records adhere to k- anonymity, which means each released record has at least (k-1) other records in the release whose values are indistinct over those fields that appear in external data. So, k- anonymity provides privacy protection by guaranteeing that each released record will relate to at least k individuals even if the records are directly linked to external information. This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity. Generalization involves replacing (or recoding) a value with a less specific but semantically consistent value. Suppression involves not releasing a value at all. The Preferred Minimal Generalization Algorithm (MinGen), which is a theoretical algorithm presented herein, combines these techniques to provide k-anonymity protection with minimal distortion. The real-world algorithms Datafly and µ-Argus are compared to MinGen. Both Datafly and µ-Argus use heuristics to make approximations, and so, they do not always yield optimal results. It is shown that Datafly can over distort data and µ-Argus can additionally fail to provide adequate protection.
---
paper_title: Matching and Record Linkage

paper_content:

This overview gives background on a number of statistical methods that have been proven effective for record linkage. To prepare data for the main computational algorithms, we need parsing/standardization that allows us to structure the free-form names, addresses, and other fields into corresponding components. The main parameter-estimation methods are unsupervised methods that yield 'optimal' record linkage parameters. Extended methods provide estimates of false match rates in both unsupervised and, with greater accuracy, in semi-supervised situations. Finally, the paper describes ongoing research for adjusting standard statistical analyses for linkage error. WIREs Comput Stat 2014, 6:313-325. doi: 10.1002/wics.1317
---
paper_title: Object Consolodation by Graph Partitioning with a Conditionally-Trained Distance Metric

paper_content:

Coreference analysis, also known as record linkage, object consolidation or identity uncertainty, is a dicult and important problem in natural language processing, databases, citation matching and many other tasks. This paper introduces several discriminative, conditional-probability models for coreference analysis, all examples of undirected graphical models. Unlike many historical approaches to coreference, the models presented here are relational—they do not assume that pairwise coreference decisions should be made independently from each other. Unlike other relational models of coreference that are generative, the conditional model here can incorporate a great variety of features of the input without having to be concerned about their dependencies— paralleling the advantages of conditional random fields over hidden Markov models. We present positive results on noun coreference in two standard text data sets.
---
paper_title: Estimating the re-identification risk per record in microdata

paper_content:

A measure of re-identification risk at the record level has a variety of potential uses in statistical disclosure control for microdata. The conceptual basis of such a measure is considered. The risk is conceived of broadly as the evidence in support of a link between the record and the unit in the population from which it is derived. For discrete key variables subject to no measurement error, a measure is derived which reflects the probability that the record is unique in the population. Under certain assumptions, two approaches are described for estimating this measure from the microdata. These approaches are applied to a 10% sample of microdata from the 1991 Census in Great Britain. It is found that the resulting risk measures can indeed be used successfully to establish whether sample unique records are unique in the population. The implications of these findings are discussed.
---
paper_title: Modelling user uncertainty for disclosure risk and data utility

paper_content:

In this paper we show how a simple model that captures user uncertainty can be used to define suitable measures of disclosure risk and data utility. The model generalizes previous results of Duncan and Lambert. We present several examples to illustrate how the new measures can be used to implement existing optimality criteria for the choice of the best form of data release.
---
paper_title: Privacy-preserving data mining

paper_content:

A fruitful direction for future data mining research will be the development of techniques that incorporate privacy concerns. Specifically, we address the following question. Since the primary task in data mining is the development of models about aggregated data, can we develop accurate models without access to precise information in individual data records? We consider the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed. The resulting data records look very different from the original records and the distribution of data values is also very different from the original distribution. While it is not possible to accurately estimate original values in individual data records, we propose a novel reconstruction procedure to accurately estimate the distribution of original data values. By using these reconstructed distributions, we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data.
---
paper_title: Achieving k-Anonymity Privacy Protection Using Generalization and Suppression

paper_content:

Often a data holder, such as a hospital or bank, needs to share person-specific records in such a way that the identities of the individuals who are the subjects of the data cannot be determined. One way to achieve this is to have the released records adhere to k- anonymity, which means each released record has at least (k-1) other records in the release whose values are indistinct over those fields that appear in external data. So, k- anonymity provides privacy protection by guaranteeing that each released record will relate to at least k individuals even if the records are directly linked to external information. This paper provides a formal presentation of combining generalization and suppression to achieve k-anonymity. Generalization involves replacing (or recoding) a value with a less specific but semantically consistent value. Suppression involves not releasing a value at all. The Preferred Minimal Generalization Algorithm (MinGen), which is a theoretical algorithm presented herein, combines these techniques to provide k-anonymity protection with minimal distortion. The real-world algorithms Datafly and µ-Argus are compared to MinGen. Both Datafly and µ-Argus use heuristics to make approximations, and so, they do not always yield optimal results. It is shown that Datafly can over distort data and µ-Argus can additionally fail to provide adequate protection.
---

Title: Masking and Re-identification Methods for Public-Use Microdata: Overview and Research Problems

Section 1: Introduction
Description 1: Introduce the paper, provide an overview of methods for masking microdata, and discuss the intent behind creating public-use files.

Section 2: Background
Description 2: Provide a framework used in disclosure avoidance research and describe various methods in use for masking microdata.

Section 3: Analytic Properties of Microdata
Description 3: Discuss issues related to ensuring that masked microdata allow users to reproduce analyses performed on original microdata, and the impact on analytic properties.

Section 4: Re-identification of Microdata
Description 4: Give an overview of methods such as record linkage and link analysis used for re-identification, and discuss the risk of re-identification.

Section 5: Discussion of Information Loss Metrics
Description 5: Review existing information loss metrics, describe their use, and address the need for developing metrics suitable for various analytic situations.

Section 6: Concluding Remarks
Description 6: Summarize the paper's coverage of methods for producing public-use microdata, their analytic uses, research problems in information-loss metrics, and evaluating re-identification risk.