Algorithms for synthetic data release under differential privacy
Jun Zhang · 2016
Releasing sensitive data while preserving privacy is an important problem that has attracted considerable attention in recent years.The state-of-the-art paradigm for addressing this problem is differential privacy, which offers a strong degree of privacy protection without making restrictive assumptions about the adversary.Most efforts to date to perform differentially private data release end up mired in complexity, overwhelm the signal with noise, and are not effective for use in practice.In this thesis, we introduce three novel solutions for complex data publication under differential privacy, namely, PrivBayes, PrivTree and the ladder framework.Compared to the previous work, our methods (i) enable the private release of a wide range of data types, i.e., multidimensional tabular data, spatial data, sequence data and graph data, (ii) improve the utility of released data by introducing significantly less perturbations in data modelling and (iii) are query-independent, such that many different queries (linear or non-linear) can be accurately evaluated on the same set of released data.First of all, we present PrivBayes, a differentially private method for releasing multidimensional tabular data.Given a dataset D, PrivBayes first constructs a Bayesian network N , which (i) provides a succinct model of the correlations among the attributes in D and (ii) allows us to approximate the distribution of data in D using a set P of lowdimensional marginals of D. After that, PrivBayes injects noise into each marginal in P to ensure differential privacy, and then uses the noisy marginals and the Bayesian network to construct an approximation of the data distribution in D. Finally, PrivBayes samples tuples from the approximate distribution to construct a synthetic dataset, and then releases the synthetic data.Intuitively, PrivBayes circumvents the curse of dimensionality, as it injects noise into the low-dimensional marginals in P instead of the full-dimensional dataset D. Private construction of Bayesian networks turns out to be significantly challenging, and we introduce a novel approach that uses a surrogate function for mutual information to build the model more accurately.We experimentally evaluate PrivBayes on real data, and demonstrate that it significantly outperforms existing solutions in terms of accuracy.Second, we introduce PrivTree, a differentially private algorithm for releasing spatial and sequential datasets.Given a set D of tuples defined on a domain Ω, PrivTree constructs a histogram over Ω to approximate the tuple distribution in D. It adopts a hierarchical decomposition approach, which recursively splits Ω into sub-domains and i I would like to express my sincere appreciation to my supervisor Dr. Xiaokui Xiao for his professional guidance and constant support throughout my Ph.D. study.It has been a wonderful experience working with Dr. Xiao in the past years, and I have greatly benefited from his insightful comments and feedback.