Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask, What concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (nonprivate) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private probabilistically approximately correct learner for the class of parity functions. This result dispels the similarity between learning with noise and private learning (both must be robust to small changes in inputs), since parity is thought to be very hard to learn given random classification noise. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Therefore, for local private learning algorithms, the similarity to learning with noise is stronger: local learning is equivalent to SQ learning, and SQ algorithms include most known noise-tolerant learning algorithms. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms. Because of the equivalence to SQ learning, this result also separates adaptive and nonadaptive SQ learning. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much larger in size than the database itself. Specifically, we give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class. ::: We also show that it is not possible to privately release even simple classes of queries (such as intervals and their generalizations) over continuous domains. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, given a slight relaxation of the utility guarantee. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension. ::: Finally, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. The sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. In either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role. For the task of sanitizing with a synthetic dataset output, we map the boundary between computational feasibility and infeasibility with respect to a variety of utility measures. For the (potentially easier) task of sanitizing with unrestricted output format, we show a tight qualitative and quantitative connection between hardness of sanitizing and the existence of traitor tracing schemes. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct improved {\em privacy-preserving synopses} of an input database. These are data structures that yield, for a given set $\Q$ of queries over an input database, reasonably accurate estimates of the responses to every query in~$\Q$, even when the number of queries is much larger than the number of rows in the database. Given a {\em base synopsis generator} that takes a distribution on $\Q$ and produces a ``weak'' synopsis that yields ``good'' answers for a majority of the weight in $\Q$, our {\em Boosting for Queries} algorithm obtains a synopsis that is good for all of~$\Q$. We ensure privacy for the rows of the database, but the boosting is performed on the {\em queries}. We also provide the first synopsis generators for arbitrary sets of arbitrary low-sensitivity queries, {\it i.e.}, queries whose answers do not vary much under the addition or deletion of a single row. In the execution of our algorithm certain tasks, each incurring some privacy loss, are performed many times. To analyze the cumulative privacy loss, we obtain an $O(\eps^2)$ bound on the {\em expected} privacy loss from a single $\eps$-\dfp{} mechanism. Combining this with evolution of confidence arguments from the literature, we get stronger bounds on the expected cumulative privacy loss due to multiple mechanisms, each of which provides $\eps$-differential privacy or one of its relaxations, and each of which operates on (potentially) different, adaptively chosen, databases. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> We present a new algorithm for differentially private data release, based on a simple combination of the Multiplicative Weights update rule with the Exponential Mechanism. Our MWEM algorithm achieves what are the best known and nearly optimal theoretical guarantees, while at the same time being simple to implement and experimentally more accurate on actual data sets than existing techniques. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> Privacy-preserving data publishing addresses the problem of disclosing sensitive data when mining for useful information. Among the existing privacy models, ∈-differential privacy provides one of the strongest privacy guarantees and has no assumptions about an adversary's background knowledge. Most of the existing solutions that ensure ∈-differential privacy are based on an interactive model, where the data miner is only allowed to pose aggregate queries to the database. In this paper, we propose the first anonymization algorithm for the non-interactive setting based on the generalization technique. The proposed solution first probabilistically generalizes the raw data and then adds noise to guarantee ∈-differential privacy. As a sample application, we show that the anonymized data can be used effectively to build a decision tree induction classifier. Experimental results demonstrate that the proposed non-interactive anonymization algorithm is scalable and performs better than the existing solutions for classification analysis. <s> BIB006 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> Privacy-preserving data publishing is an important problem that has been the focus of extensive study. The state-of-the-art solution for this problem is differential privacy, which offers a strong degree of privacy protection without making restrictive assumptions about the adversary. Existing techniques using differential privacy, however, cannot effectively handle the publication of high-dimensional data. In particular, when the input dataset contains a large number of attributes, existing methods require injecting a prohibitive amount of noise compared to the signal in the data, which renders the published data next to useless. To address the deficiency of the existing methods, this paper presents P riv B ayes , a differentially private method for releasing high-dimensional data. Given a dataset D, P riv B ayes 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 low-dimensional marginals of D. After that, P riv B ayes 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, P riv B ayes samples tuples from the approximate distribution to construct a synthetic dataset, and then releases the synthetic data. Intuitively, P riv B ayes circumvents the curse of dimensionality, as it injects noise into the low-dimensional marginals in P instead of the high-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 P riv B ayes on real data and demonstrate that it significantly outperforms existing solutions in terms of accuracy. <s> BIB007 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> Releasing high-dimensional data enables a wide spectrum of data mining tasks. Yet, individual privacy has been a major obstacle to data sharing. In this paper, we consider the problem of releasing high-dimensional data with differential privacy guarantees. We propose a novel solution to preserve the joint distribution of a high-dimensional dataset. We first develop a robust sampling-based framework to systematically explore the dependencies among all attributes and subsequently build a dependency graph. This framework is coupled with a generic threshold mechanism to significantly improve accuracy. We then identify a set of marginal tables from the dependency graph to approximate the joint distribution based on the solid inference foundation of the junction tree algorithm while minimizing the resultant error. We prove that selecting the optimal marginals with the goal of minimizing error is NP-hard and, thus, design an approximation algorithm using an integer programming relaxation and the constrained concave-convex procedure. Extensive experiments on real datasets demonstrate that our solution substantially outperforms the state-of-the-art competitors. <s> BIB008 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Synthetic Dataset Publishing <s> A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries are of the form “What fraction of individual records in the database satisfy the property $q$?” We prove that if one-way functions exist, then there is no algorithm that takes as input a database $D \in (\{0,1\}^d)^n$, and $k = \tilde{\Theta}(n^2)$ arbitrary efficiently computable counting queries, runs in time $\mathrm{poly}(d, n)$, and returns an approximate answer to each query, while satisfying differential privacy. We also consider the complexity of answering “simple” counting queries, and make some progress in this direction by showing that the above result holds even when we require that the queries are computable by constant-depth $(AC^0)$ circuits. Our result is almost tight because it is known that $\tilde{\Omega}(n^2)$ counting queries can be answered efficiently while satisfying differential privacy. Mor... <s> BIB009
Synthetic dataset publishing investigates publishing datasets with the public instead of sharing answers to queries. Suppose the input dataset is D with d attributes, and the curator would like to publish a synthetic b D that can be used to answer a query set F . Two different methods to achieve this goal exist. One method applies anonymization techniques to publish an anonymized dataset, which retains the same records as the original dataset. Another method takes samples from the data universe to build a synthetic dataset, which follows the original datasets distribution but may not necessarily keep the same records. Synthetic dataset publishing based on anonymization. This line of works observes that if the anonymization process follows the requirement of differential privacy at each step, the published synthetic dataset will satisfy differential privacy. Based on this observation, Mohammed et al. BIB006 proposed the anonymized algorithm DiffGen to preserve privacy for data mining purposes. The anonymized procedure consists of two major steps: partitioning and perturbation. Every attribute of the original dataset is generalized to its top-most state. The partitioning step then splits these attributes into more specific groups according to the attribute taxonomy trees. It applies an exponential mechanism to choose a candidate for the specialization. After that, random noise is added to the true count of each records group by perturbation. Synthetic dataset publishing based on learning theory. Kasiviswanathan et al. BIB001 and Blum et al. BIB002 claim that if a query on a published dataset is limited to a particular concept set C, the learning process can ensure the accuracy of the query answer in the constraint of differential privacy. Kasiviswanathan et al. BIB001 proposed an exponential based mechanism to search a synthetic dataset from the data universe that can accurately predict C. Fig. 4 shows that after creating multiple candidate datasets from the data universe, the mechanism will search the most suitable b D based on the exponential mechanism. The authors claimed that for any C and any D ! f0; 1g d , if the size of the dataset satisfies a accuracy can be achieved with a probability of 1 À b. Subsequent works made progress toward improving accuracy. Dwork et al. BIB004 used boosting to improve the lower bound of accuracy to Oð ffiffiffiffiffiffiffiffiffiffiffi ffi nlog jX j p log 2=3 m Þ. Hardt et al. BIB005 combined an exponential mechanism with a multiplicative weight iteration approach to achieve a nearly optimal accuracy guarantee. Although these mechanisms developed tight bounds on accuracy, they suffer from inefficient computation time. A normal time cost is exponential in the size of universe X and the size of concept class C. Blum et al. BIB002 claim that if polynomial time is required, the definition of privacy has to be relaxed. This claim was confirmed by Dwork et al. BIB003 , who proved that only after relaxing the notion of to ð; dÞ can computational time be polynomial. Moreover, Ullman et al. BIB009 showed that among all computationally efficient algorithms, the Laplace mechanism is almost optimal. In fact, no algorithm has the ability to answer more than Oðn 2 Þ queries randomly in polynomial time. This result suggests that it is difficult to design mechanisms to answer arbitrary queries efficiently. Table 9 summarizes the key works on ynthetic datasets. For simplicity, sensitivity is predefined as 1, the dependence on b is omitted and the run-time only considers the size of the universe. Learning theory extends the research work on synthetic data releases, proving it is possible to maintain acceptable utility while preserving differential privacy. Nevertheless, the issue of reducing the computational complexity remains a challenge. Synthetic dataset publishing for high dimensional datasets. Neither anonymized dataset publishing nor learning theorybased publishing can effectively handle high-dimensional datasets. In anonymized methods, when the input dataset contains many attributes, existing anonymized methods will inject a prohibitive amount of noise, which leads to inferior utility. In learning theory-based methods, computational complexity is exponential to the dimension of the dataset, making the publication infeasible for high-dimensional datasets. One promising way to address high dimensionality is to disassemble the dataset into a group of lower dimensional marginal datasets, and then apply methods to infer the joint data distribution from these marginal datasets. Zhang et al. BIB007 followed the above rationale and used a Bayesian network to deal with high dimensionality. They assumed some correlations between attributes exist and, if these correlations can be modeled, the model can be used to generate a set of marginal datasets to simulate the distribution of the original dataset. The disadvantage of this solution is that it consumes too much of the privacy budget during network construction and, hence, makes the approximation of the distribution inaccurate. Chen et al. BIB008 addressed this disadvantage by proposing a clustering method. They disclose the pairwise correlation of all the attributes and generate a dependency graph. A junction tree algorithm is applied to the graph to identify a set of attribute clusters, which are used to generate noisy marginals. As a final step, an inference model is used to create a synthetic dataset. As opposed to BIB007 , they have limited access to the dataset, saving the privacy budget to obtain a better result.