Interactive privacy via the median mechanism

By Aaron Roth, Tim Roughgarden. 2009

291 citations recorded by the source corpus.

We define a new interactive differentially private mechanism --- the median mechanism --- for answering arbitrary predicate queries that arrive online. Given fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the Laplace mechanism, which independently perturbs each query result). With respect to the number of queries, our guarantee is close to the best possible, even for non-interactive privacy mechanisms. Conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting. We also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. This efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input distributions. The dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, methodology): “Collect the data unencrypted: One way to implement the SVT would be to simply have the aggregator collect all the data unencrypted, and to perform the thresholding at the ag-gregator.”
Tight Lower Bounds for Differentially Private Selection (2017, background): “Selection problems appear in many natural statistical problems, including private multiple hypothesis testing [1], sparse linear regression [2], [3], finding frequent itemsets [4], and as subroutines in algorithms for answering exponentially many statistical queries [5], [6], [7], [8], [9], approxim”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “The work of [25] considers scenarios when many predicate queries are asked against the same dataset, and it uses an approach that, rather than providing randomization for each answer separately, attempts to reconstruct the answer to some queries based on the answers previously given to other…”
Scalable Private Learning with PATE (2018, methodology): “There is previous work in differential privacy literature (Hardt & Rothblum, 2010; Roth & Roughgarden, 2010) where the mechanism first decides whether or not to answer a query, and then privately answers the queries it chooses to answer using a traditional noiseaddition mechanism.”
Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “[20]; several refinements were proposed by Hardt and Rothblum [30], Roth and Roughgarden [44].”
Algorithmic stability for adaptive data analysis (2015, methodology): “For arbitrary low-sensitivity queries, the Gaussian or Laplace Mechanism is again optimal when k is small, and for large k we can use the Median Mechanism [RR10].”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “Most crucially, it is known how to accurately answer exponentially many adaptively chosen queries on a fixed dataset while preserving differential privacy [38, 25], which is what yields the main application in our paper, when combined with our main theorem.”
Universally utility-maximizing privacy mechanisms (2008, neutral): “, with low Vapnik–Chervonenkis (VC) dimension) [6, 16, 22].”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “Their work was improved on in several important aspects [16, 19, 30, 25, 22, 24].”
Between Pure and Approximate Differential Privacy (2015, methodology): “Our algorithm for approximate di ﬀ erential privacy makes use of a powerful tool from the literature [DNR + 09, HR10, DNPR10, RR10] called the sparse vector algorithm: Theorem 4.2 (Sparse Vector) .”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “[HR10] and its various extensions [HLM10, GHRU11, GRU12]; the Median Mechanism [RR10] and a boosting mechanism of Dwork et al [DRV10].”
Understanding the Sparse Vector Technique for Differential Privacy (2016, methodology): “The algorithms in [16, 12] also has another difference, as discussed in Sect ion 3.”
Private Multiplicative Weights Beyond Linear Queries (2014, background): “Fortunately, for many interesting types of queries, there are remarkable differentially private algorithms [5, 12, 15, 26, 19, 17, 18] that are capable of giving accurate answers to exponentially many different queries—far greater than what can be achieved using straightforward composition.”
Simultaneous Private Learning of Multiple Concepts (2015, background): “One surprising result in differential privacy is that it is possible to answer an exponential number of such queries on a dataset [8, 25, 20].”