# Tag Info

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 ...
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 ...
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 ...
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 ...

### 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 ...
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 ...

### 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 ...
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"), ...
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$$ ...

### 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 ...
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 ε, ...
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 ...
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 ...

### 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. ...
Accepted

### 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 ...
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 ...
### 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 ...