Construction of Microdata from a Set of Differentially Private Low-dimensional Contingency Tables through Solving Linear Equations with Tikhonov Regularization
Evercita C. Eugenio, Fang Liu · arXiv (Cornell University) · 2018
When individual-level data are shared for research and public use, they are often perturbed to provide some level of privacy protection. A simple way to perturb a high-dimensional data set where individual-level data can be easily generated with good utility is to sanitize the full contingency table or full-dimensional histogram. However, it can be costly from the data storage and memory perspective to work with full tables. In addition, most of the observed signals in the high-order interactions among all attributes are likely just sample randomness rather than being of statistical significance and rarely of interest to practitioners. We introduce a new algorithm, CIPHER, which can reproduce individual-level data from a set of meaningful differentially private low-dimensional contingency (LDC) tables constructed from the original high-dimensional data, through solving a set of linear equations with the Tikhonov regularization. CIPHER is conceptually simple and requires no more than decomposing joint probabilities via basic probability rules to construct the equation set and subsequently solving linear equations. Compared to full table sanitization, the set of LDC tables that CIPHER works with has drastically lower requirements on data storage and memory. We run experiments to compare CIPHER with the full table sanitization and the multiplicative weighting exponential mechanism (MWEM) which can also be used to generate individual-level synthetic data given a set of LDC tables.The results demonstrate that CIPHER outperforms MWEM in preserving original information at the same privacy budget and converges to the full-table sanitization in utility as the sample data size or the privacy budget increases.