A scheme that publishes aggregate information about sensitive data must resolve the trade-off between utility to information consumers and privacy of the database participants. Differential privacy is a well-established definition of privacy--this is a universal guarantee against all attackers, whatever their side-information or intent. In this paper, we present a universal treatment of utility based on the standard minimax rule from decision theory (in contrast to the utility model in, which is Bayesian). In our model, information consumers are minimax (risk-averse) agents, each possessing some side-information about the query, and each endowed with a loss-function which models their tolerance to inaccuracies. Further, information consumers are rational in the sense that they actively combine information from the mechanism with their side-information in a way that minimizes their loss. Under this assumption of rational behavior, we show that for every fixed count query, a certain geometric mechanism is universally optimal for all minimax information consumers. Additionally, our solution makes it possible to release query results at multiple levels of privacy in a collusion-resistant manner.
A recent thorough survey of the state of the field of differential privacy is given in @cite_14 . Dinur and Nissim @cite_23 , @cite_19 establish upper-bounds on the number of queries that can be answered with reasonable accuracy. Most of the differential privacy literature circumvents these impossibility results by focusing on interactive models where a mechanism supplies answers to only a sub-linear (in @math ) number of queries. Count queries (e.g. @cite_23 @cite_15 ) and more general queries (e.g. @cite_8 @cite_10 ) have been studied from this perspective.
@cite_14 @cite_8 @cite_19 @cite_23 @cite_15 @cite_10
2962958653 2099259603 2017509273 83413860
In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by [Lecture Notes in Comput. Sci. 3876, Springer, New York, 2006, pp. 265--284] that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private probably approximately correct (PAC) and agnostic learning was studied in a number of prior works starting with [SIAM J. Comput., 40 (2011), pp. 793--826]. However, a number of basic questions remain open [A. Beimel, S. P. Kasiviswanathan, and K. Nissim, Lecture Notes in Comput. Sci. 5978, Springer, New York, 2006, pp. 437--454; K. Chaudhuri and D. Hsu, Proceedings of Conference in Learning Theory, 2011, pp. 155--186; A. Beimel, K. Nissim, and U. Stemmer, Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, 2013, pp. 9... Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. But despite much recent work, optimal strategies for answering a collection of related queries are not known. We propose the matrix mechanism, a new algorithm for answering a workload of predicate counting queries. Given a workload, the mechanism requests answers to a different set of queries, called a query strategy, which are answered using the standard Laplace mechanism. Noisy answers to the workload queries are then derived from the noisy answers to the strategy queries. This two stage process can result in a more complex correlated noise distribution that preserves differential privacy but increases accuracy. We provide a formal analysis of the error of query answers produced by the mechanism and investigate the problem of computing the optimal query strategy in support of a given workload. We show this problem can be formulated as a rank-constrained semidefinite program. Finally, we analyze two seemingly distinct techniques, whose similar behavior is explained by viewing them as instances of the matrix mechanism. Existing differential privacy (DP) studies mainly consider aggregation on data sets where each entry corresponds to a particular participant to be protected. In many situations, a user may pose a relational algebra query on a database with sensitive data, and desire differentially private aggregation on the result of the query. However, no existing work is able to release such aggregation when the query contains unrestricted join operations. This severely limits the applications of existing DP techniques because many data analysis tasks require unrestricted joins. One example is subgraph counting on a graph. Furthermore, existing methods for differentially private subgraph counting support only edge DP and are subject to very simple subgraphs. Until recent, whether any nontrivial graph statistics can be released with reasonable accuracy for arbitrary kind of input graphs under node DP was still an open problem. In this paper, we propose a novel differentially private mechanism that supports unrestricted joins, to release an approximation of a linear statistic of the result of some positive relational algebra calculation over a sensitive database. The error bound of the approximate answer is roughly proportional to the empirical sensitivity of the query --- a new notion that measures the maximum possible change to the query answer when a participant withdraws its data from the sensitive database. For subgraph counting, our mechanism provides a solution to achieve node DP, for any kind of subgraphs. Differential privacy has emerged as one of the most promising privacy models for releasing the results of statistical queries on sensitive data, with strong privacy guarantees. Existing works on differential privacy mostly focus on simple aggregations such as counts. This paper investigates the spatial OLAP queries, which combines GIS and OLAP queries at the same time. We employ a differentially private R-tree(DiffR-Tree) to help spatial OLAP queries. In our method, several steps need to be carefully designed to equip the spatial data warehouse structure with differential privacy requirements. Our experiments results demonstrate the efficiency of our spatial OLAP query index structure and the accuracy of answering queries.