This is a paper about private data analysis, in which a trusted curator holding a confidential database responds to real vector-valued queries. A common approach to ensuring privacy for the database elements is to add appropriately generated random noise to the answers, releasing only these noisy responses. A line of study initiated in [DN03] examines the amount of distortion needed to prevent privacy violations of various kinds. The results in the literature vary according to several parameters, including the size of the database, the size of the universe from which data elements are drawn, the "amount" of privacy desired, and for the purposes of the current work, the arity of the query. In this paper we sharpen and unify these bounds. + 10] to obtain linear lower bounds on distortion when providing differential privacy for a (contrived) class of low-sensitivity queries. (A query has low sensitivity if the data of a single individual has small effect on the answer.) Several structural results follow as immediate corollaries: • We separate so-called counting queries from arbitrary low-sensitivity queries, proving the latter requires more noise, or distortion, than does the former; • We separate (ε, 0)-differential privacy from its well-studied relaxation (ε, δ)-differential privacy, even when δ ∈ 2 −o(n) is negligible in the size n of the database, proving the latter requires less distortion than the former; • We demonstrate that (ε, δ)-differential privacy is much weaker than (ε, 0)-differential privacy in terms of mutual information of the transcript of the mechanism with the database, even when δ ∈ 2 −o(n) is negligible in the size n of the database. We also simplify the lower bounds on noise for counting queries in [HT10] and also make them unconditional. Further, we use a characterization of (ǫ, δ) differential privacy from [MMP + 10] to obtain lower bounds on the distortion needed to ensure (ε, δ)-differential privacy for ǫ, δ > 0. Next, we revisit the LP decoding argument of [DMT07] and combine it with recent results of Rudelson [Rud11] to show that for some specific η > 0, if the ℓ-way marginals are released such that at least 1 − ǫ fraction of the entries have o( √ n) noise, then a very minimal notion of privacy called attribute privacy is violated. This improves on a recent result of Kasiviswanathan et al. [KRSU10] where the same conclusion was shown assuming that all the entries have o( √ n) noise. Finally, we extend the original lower bound of [DN03] to prevent blatant non-privacy to the case when the universe size is smaller than the size of the database. As we show, the lower bound on the noise required to prevent blatant non-privacy becomes larger as the size of the universe decreases.
De REF studies lower bound on the additive noise for Lipschitz query functions in ( , δ)-differential privacy which uses a different metric for the noise, and the lower bound depends on the size of the database.
Lower bounds in differential privacy
ArXiv
ArXiv
Computer Science