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


7

The other answers are good but I thought I would systemize the differences with a single example. Say Bob has a database with 10 entries of the form {name, salary} and Alice would like to query it. With PIR, Alice can retrieve any entry or entries of her choosing (say the 8th entry) without Bob learning which one. The trivial PIR is Alice just retrieves ...


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

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


3

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


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

In differential privacy the concern is to protect the privacy of a single row of the database. Informally, the DP concept says that everything that can be learned from the database could be learned without access to that row. In a more technical sense, a mechanism respects this property if the distribution of the answers is almost identical (in a very strict ...


3

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


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

There is a slight distinction between PIR and OT. From Wikipedia: PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items. In other words, OT is stronger in that the receiver only gets what is requested. Differential privacy is new to me, so I'll read up on ...


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

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


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

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


1

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 your original data was completely different, you would not be able to tell the difference just by looking at the model. Your data is effectively indiscernible ...


1

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


1

Your conjecture seems correct. If the sets are disjoint then the mapping $\bar{M} = (M_1,\dots,M_n)$ is $(\max(\epsilon_i),\max(\delta_i))$-DP. Note that for every database $D$ and any $x$, $\bar{M}(D)$ differs from $\bar{M}(D\setminus {x})$ in only one coordinate by the disjoint assumption, w.l.o.g., they differ in the $j$'th coordinate. Therefore, the ...


1

In order to bridge the gap between two worst case scenarios to produce similar distribution of privatized answers certain noise is added. For example the salaries of a CEO (max) and a line worker or who ever gets minimum wage (min) may not be produce similar distribution without the noise. Random values taken from Laplacian distribution with standard ...


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