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 ...
Ted's user avatar
  • 1,008
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 ...
Shan Chen's user avatar
  • 2,715
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 ...
Ted's user avatar
  • 1,008
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 ...
Mark Schultz-Wu's user avatar
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 ...
Squeamish Ossifrage's user avatar
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 ...
Frank McSherry's user avatar
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 ...
Shan Chen's user avatar
  • 2,715
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$$ ...
Nikos Fotiou's user avatar
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"), ...
Ted's user avatar
  • 1,008
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 ...
Ted's user avatar
  • 1,008
4 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 ...
Piggy Wenzhou's user avatar
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 ε, ...
Mikero's user avatar
  • 13.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 ...
Ted's user avatar
  • 1,008
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 ...
Yehuda Lindell's user avatar
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 $...
kodlu's user avatar
  • 22.5k
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 $\...
Ted's user avatar
  • 1,008
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. ...
Ted's user avatar
  • 1,008
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 ...
kodlu's user avatar
  • 22.5k
3 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 ...
Ted's user avatar
  • 1,008
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 ...
Kunal's user avatar
  • 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$, $\...
Léo Colisson's user avatar
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 ...
Mark Schultz-Wu's user avatar
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 ...
Ted's user avatar
  • 1,008
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 ...
Thomas's user avatar
  • 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 ...
Thomas's user avatar
  • 151
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 ...
Mark Schultz-Wu's user avatar
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 ...
Ted's user avatar
  • 1,008
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 ...
Ted's user avatar
  • 1,008
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$, ...
Daniel S's user avatar
  • 23.8k
2 votes
Accepted

Multiple attributes under shuffled differential privacy

The theorem in the paper you refer to only assumes that $\varepsilon<1$ because it simplifies the analysis & the proof — amplification happens regardless of the value of $\varepsilon$. If you ...
Ted's user avatar
  • 1,008

Only top scored, non community-wiki answers of a minimum length are eligible