13
votes
Accepted
Intuitive explanation of the $\varepsilon$ parameter in differential privacy
A colleague gave me the following explanation that I think makes a lot of intuitive sense, so I'm reproducing it here. Skip to the last paragraph it you don't care about the proof.
Suppose you're ...
- 988
8
votes
Accepted
Difference between ε-differential privacy and (ε, δ)-differential privacy
The $\delta$ item is a relaxation of the $\epsilon$-differential privacy notion. The latter is a strong security notion because it requires an algorithm $\mathcal{A}$ to have very close output ...
- 2,685
6
votes
Accepted
Differential Privacy: why $\delta$ negligible on the row numbers?
$\varepsilon$-differential privacy is absolute: for any pair of databases, you cannot gain more than a small amount of probabilistic information about a single individual. When you add or remove an ...
- 988
6
votes
Accepted
Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity
I haven't read your full question, but the answer to:
Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?
and (implicitly)
Can the ...
- 10.8k
5
votes
What does the term "differential" in "differential privacy" mean?
The term "differential" was proposed by Mike Schroeder, to characterize the guarantee as being a relationship between distributions with and without any input record. At the time most papers simply ...
5
votes
Accepted
Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive？
In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published.
Consider a malicious algorithm $M^*$ that ...
- 2,685
5
votes
Differential privacy on medical data
Differential privacy does not help to prevent disclosure of individual records when the user—the doctor, in this case—needs access to the individual records themselves.
Differential privacy is a ...
- 47.2k
4
votes
Accepted
Differential privacy per record
Yes, the classic example is Randomized response: when doing a survey with a yes/no question that is sensitive (for example, "are you currently an undocumented immigrant living in the US"), ...
- 988
4
votes
Accepted
Differential privacy of "randomized responses"
I found the answer in this book https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf at page 30
Fix a respondent. A case analysis shows that
$$Pr[Response = Yes|Truth = Yes] = 3/4$$
...
- 93
4
votes
What does the term "differential" in "differential privacy" mean?
On the first question — see Frank McSherry's answer.
On the second question, no, these are largely unrelated concepts. Local vs. global DP refers to the context in which DP is applied: whether there ...
- 988
4
votes
Accepted
How do we select values for parameters when using Differential Privacy?
In the 2019 paper Differential Privacy in Practice: Expose Your Epsilons!, the authors Dwork, Kohli, Mulligan summarize the state of affairs thusly:
We found no clear consensus on how to choose ε, ...
- 11.2k
3
votes
Accepted
Laplace mechanism in Differential Privacy
These two formulas are the same thing. The second formula is the probability density function of the Laplace distribution centered on 0 ($\mu=0$) — although rather than $Pr[v]$, the second PDF should ...
- 988
3
votes
Accepted
How is it possible to define differential privacy on two databases that differ more than a single entry?
One of the advantages of differential privacy is composition. That is, if $D_1$ and $D_k$ differ on $k$ entries, then $k\cdot\epsilon$ differential privacy is achieved. This is easily shown by writing ...
- 27.4k
3
votes
what is the relationship between epsilon and sensitivity in the Differential-Privacy?
I'll answer the second question first. The two are distinct concepts — there's no way directly compare graphs or results without more info or context.
Differential privacy is usually obtained by 1. ...
- 988
3
votes
Accepted
What's the meaning of probabilities in differential privacy formula?
No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms.
For simplicity, assume there are $N$ randomized functions $...
- 19.9k
3
votes
Differential privacy on multiple queries – what is the behavior?
It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\...
- 988
3
votes
Proof of the basic differential privacy composition theorem
You are right, we need to assume the coin toss of mechanisms are independent to each other, as stated in the proof.
You are right, again. The proof in the paper seems to be problematic. Here's the ...
- 163
3
votes
Accepted
Lemma KL-Divergence (Differential Privacy)
I don't understand why:
$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$
Well the domain is partitioned into $T$ and its complement. So the sum over the full domain of the ...
- 19.9k
3
votes
Accepted
Differential privacy noise that scales with $L_p$-sensitivity with $p>2$?
You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more ...
- 46
3
votes
Differential privacy what does "where the probability is taken over the randomness used by the algorithm" mean?
So here $\mathcal{M}$ is, as you wrote, a "randomized mechanism", so it means that for one entry $D$ it can output different values. For example, you can imagine that on entry $D = 1$, $\...
- 1,096
3
votes
Advanced Composition in DP is worse than Basic Composition
First, there are other composition results, for example I believe this one improves on advanced composition.
I'll answer a more general question though (which I think you are getting at).
Given ...
- 10.8k
2
votes
What is ε in differential privacy?
In ε-differential privacy, ε represents the privacy parameter.
You might want to try to enhance your research efforts because related papers and publications ...
- 17.7k
2
votes
what does differential privacy (in machine learning) promise or guarantee?
Model inversion attacks are, by definition, impossible if the model generation process is $\epsilon$-differentially private for a sufficiently small $\epsilon$: differential privacy guarantees that if ...
- 988
2
votes
Why does ε-differential privacy protect the subset of 1/ε edges in terms of graphs?
I think this is a reference to group privacy. See Theorem 2.2 in the Dwork-Roth book.
If you have $(\varepsilon,0)$-differential privacy for changing 1 edge, then you have $(1,0)$-differential ...
- 151
2
votes
Interpretation of advanced composition theorem of differential privacy
Consider the composition of $k$ algorithms each of which is $(\varepsilon,0)$-differentially private. We want to calculate parameters $\varepsilon'$ and $\delta'$ such that that the composition of ...
- 151
2
votes
Accepted
$(\epsilon, \delta)$-differential privacy: main motivation of $\delta$
I help implement and ship anonymization strategies based on differential privacy in a large tech company. In my experience, the $\delta$ is mainly used for two reasons.
Partition selection: when ...
- 988
2
votes
Accepted
Sensitivity on differential privacy
The differential privacy book is the typical reference for the area, and it is quite useful here. Since this answer essentially amounts to quoting from that book, I'll walk through how to find the ...
- 10.8k
2
votes
Accepted
Differential Privacy: is the bound for group privacy tight?
Yes, this bound is tight.
The optimal partition selection mechanism introduced in this paper achieves the bound: every step "uses up" all the $(\varepsilon,\delta)$ budget available, and for ...
- 988
2
votes
Accepted
How to adapt the equation of Gaussian mechanism noise based on number of executions
The formula you mention to get $\sigma$ given $\delta$ and $\varepsilon$ is only correct for $\varepsilon<1$. It's also not tight.
If you use Gaussian noise on multiple statistics, each of ...
- 988
2
votes
Can Differential Privacy be used to show that two distributions are indistinguishable?
These sorts of arguments come up in the theory of randomness extractors where we argue that a random function from a certain family when applied to inputs with a certain minimum entropy ($H_\infty$, ...
- 20k
Only top scored, non community-wiki answers of a minimum length are eligible