8

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 trying to track one individual user, and you're trying to figure out whether they're in the database. You have some prior knowledge about this: $\frac{P(in)}{P(out)...


5

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 property of a system for aggregating a collection of records into statistical queries on a data set so that the inclusion or exclusion of an individual record can't ...


5

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 picks a random individual's record from the input database (of size $n$) and outputs it. Note that this $M^*$ should not be considered secure for a good ...


5

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 distributions on "neighbor" datasets $D_1,D_2$ that differ in a single record. From its formal definition $\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\...


4

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$$ Specifically, when the truth is “Yes” the outcome will be “Yes” if the first coin comes up tails (probability 1/2) or the first and second come up heads (...


4

$\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 individual in your database, all possible outputs of your algorithm can appear with similar probability. By contrast, $(\varepsilon,\delta)$-differential privacy ...


4

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 defined "(x,y,z)-privacy as ..." and the work felt of a sufficiently different character (both weaker and stronger than prior work) to call out the distinction. ...


3

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 is a central aggregator that knows the data of all individuals, or whether each individual adds noise to their own data before passing it on to the aggregator. ...


3

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 a series of equations. Specifically, let $D_1$ and $D_k$ differ on $k$ entries, and let $D_i$ be a database that differs from $D_{i-1}$ on one entry (for $i=2,....


3

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 $\mathcal{K}$ possible, and one choose one uniformly with probability $1/N.$ For example, if we restricted ourselves to polynomials of degree $\leq k$ over $...


3

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 difference of the two probability distributions is zero. $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0,$$ but now you can just ...


2

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"), you ask each respondent to flip a coin first. If the coin hits tails, you tell them to answer randomly (by flipping a second coin), otherwise, ask them to answer honestly. ...


2

In ε-differential privacy, ε represents the privacy parameter. You might want to try to enhance your research efforts because related papers and publications mention that more than frequently. Even websites like Wikipedia would have quickly provided you with an answer to your question. Quoting Wikipedia > Differential privacy > ε-differential privacy > ...


2

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 $\varepsilon_i$ to the total $\varepsilon$ of the entire process: $\varepsilon=\sum_i\varepsilon_i$. So "session" probably means "single query" in the context of ...


2

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. computing a function $F$ of the data and 2. adding some noise to the result. The noise must be large enough to hide an individual contribution, and "how well an ...


2

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 privacy for changing $1/\varepsilon$ edges.


2

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 these algorithms satisfies $(\varepsilon',\delta')$-differential privacy. The comparison is between advanced composition $$\varepsilon' = \sqrt{2k\log(1/\delta)}\...


2

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 probably have used a notation like $f(v)$ to make it clear that this is a probability density function and not the probability of returning exactly $v$. If the ...


2

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 modified proof: \begin{align} Pr[(x_1, x_2) \in S] &= Pr[x_1 \in S_1] Pr[x_2 \in S_2 | x_1 \in S_1] \\ &\le (\min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in ...


2

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 right things to quote. Ctrl+F-ing "Laplace", we find Theorem 3.6, which states that the Laplace mechanism is $(\epsilon,0)$-differentially private. This ...


1

The Laplace mechanism only works for deterministic $f$, because the notion of "sensitivity" (the $\Delta f$ in the formulas above) isn't well-defined for random functions. $\Delta f$ is the maximum difference between $f(x)$ and $f(y)$, for neighboring $x$ and $f$. If $f$ is a random function, then that notion of "difference" becomes much ...


1

I had the same problem when I was understanding this because it's not so intuitive. I will answer here in case future people had the same trouble. Agree with you $\Delta B$ assigns a probability to every element of the set $B$. $A$ It can be anything I assume from continuos to discrete objects. $(M(a))_b$ is the probability that the mechanism outputs $b$ ...


1

When we look at the definition of Differencial Privacy in the Dwork papers, e.g. The Algorithmic Foundations of Differential Privacy, we have that a $\epsilon$-Differential Privacy for algorithm $M$ as: $$Pr[M(x_1) \in S] \leq e^\epsilon Pr[M(x_2) \in S]$$ with $S \subseteq range(M)$, for any two neighboring data sets $x_1,x_2$, differing by the addition ...


1

Yes. $\varepsilon$-differential privacy with $\varepsilon=0$ implies that the output of the mechanism must be independent of the input -- i.e., it provides no information whatsoever.


1

I think what you are looking for is "Perceptual Hashing". What I understand from your question is that you need a way for programmatically identifying images even when they have been manipulated beyond human recognition. Their is a Microsoft project called PhotoDNA. I believe the have a cloud API. You may also want to look at this Python example


1

By allowing a slack in $\tilde \delta$, one can get a higher privacy of $\tilde \epsilon = O(k \epsilon^2 + \sqrt{k}\epsilon)$, compared with the basic composition $\tilde \epsilon = O(k\epsilon)$. That's the advantage of advanced composition theorem. Of course when $\tilde \delta$ close to 0 it is very likely that advanced composition guarantee will be ...


1

Differential privacy is a property of an algorithm (or if you like, a probability distribution over functions), not a property of either the inputs or the outputs of that algorithm. The definition of differential privacy has a universal quantifier over its inputs: for all pairs of inputs that differ in at most one record, the probabilities of any outcome ...


1

In Salil Vadhan's textbook The Complexity of Differential Privacy the author states in section 1.4 The choice of a multiplicative measure of closeness between distributions is important, and we will discuss the reasons for it later. It is technically more convenient to use $e^\epsilon$ instead of $(1 + \epsilon)$, because the former behaves more nicely ...


1

The definition of Laplace Mechanism: $$ \mathcal{M}_L(x, f(\cdot), \varepsilon) = f(x) + (Y_1,\ldots,Y_k) $$ Once each $Y_i \sim Lap(\Delta f/\varepsilon)$ they are indepedent of each other. So we can calcule the joint probability of them using the product of marginals. As we know $p_x = \mathcal{M}_L(x,f,\varepsilon)$ and $z \in \mathbb{R}^k$, thus is ...


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