Questions tagged [differential-privacy]

Differential privacy aims to provide means to maximize the accuracy of queries from statistical databases while minimizing the chances of identifying its records.

Filter by
Sorted by
Tagged with
3
votes
1answer
25 views

Lemma KL-Divergence (Differential Privacy)

I am studying differential privacy and I got stuck again in proof of a lemma. Which is: $D_{\infty}^\delta(Y||Z) \leq \epsilon$ if and only if there exists a random variable $Y'$ such that $\Delta(Y,...
1
vote
0answers
23 views

Calculating the privacy that Renyi ($\epsilon, \delta$) Differential Privacy satisfies

I add differential privacy (DP) to my machine learning models by using PyTorch-DP. PyTorch-DP supplies me with the values: $\epsilon$ and $\delta $. I know that the $\epsilon$ tells us something about ...
2
votes
1answer
75 views

Differential Privacy: What is the 'game' between data holder and adversary?

I have been reading the Differential Privacy (DP) literature for some time to get familiar with it. I feel comfortable with the Math and Stats foundations of it, but I am suffering a bit from the '...
0
votes
1answer
29 views

Differential privacy basics: Universe \mathcal{X} and database $x$

The "Algorithmic Foundations of Differential Privacy" book (DOI: 10.1561/0400000042) introduces formally the "universe" and "database" on page 17 roughly as: $\mathcal{X}$ is a universe databases $x$ ...
0
votes
0answers
40 views

Proof of the basic differential privacy composition theorem

The basic composition theorem in differential privacy states, that if I have mechanisms $M_1$, which is $(\epsilon_1, \delta_1)$-differential private, and $M_2$, which is $(\epsilon_2, \delta_2)$-...
0
votes
1answer
42 views

Differential Privacy of the Laplace mechanism with non-deterministic function

This question is about the proof of the differential privacy of the laplace mechanism. All more detailled explanations I found of the proof, that the laplace mechanism is $\epsilon$-differentially ...
0
votes
1answer
30 views

Laplace mechanism in Differential Privacy

From The Algorithmic Foundations of Differential Privacy It wrote that : But from this pdf I am confused which one is right, or I misunderstand. In second method, after I compute Pr[v], and then ...
1
vote
1answer
41 views

Confusing notation in the definition of differential privacy

I've started looking into differential privacy from scratch following "The Algorithmic Foundations of Differential Privacy" by Dwork and Roth (freely available online). The mathematical notation is ...
0
votes
2answers
61 views

What is the implication for differential privacy if $\epsilon = 0$?

In pure differential privacy, the parameter $\epsilon$ represents the desired privacy loss. The smaller the $\epsilon$ is, the more privacy we can obtain. What happens when we want the privacy loss $\...
0
votes
1answer
43 views

Adding the same noise to all element of a vector is Differential privacy

In Differential privacy, if we add a $N$-dimension private vector with $N$-dimension Laplace or Gauss noise, we obtain differential privacy. However, if we only generate a 1-dimension noise to add it ...
1
vote
0answers
38 views

Norms in differential privacy

I know that perturbation should be proportional to the $\text{L}_1$-sensitivity of the function if someone wants ($\epsilon,0$)-differential privacy, and proportional to the $\text{L}_2$-sensitivity ...
0
votes
1answer
32 views

questions about sensitivity in differential privacy

Ted here (What does the term "differential" in "differential privacy" mean?) describes the difference between local and global sensitivity as "By contrast, local and global ...
0
votes
0answers
29 views

Why does Gausian use less noise than Laplace

Why does Gaussian noise apply less noise than Laplace? has to do maybe that Laplace is been used with queries and each query may have different sensitivity? or maybe because Gaussian is been used on ...
6
votes
2answers
156 views

What does the term “differential” in “differential privacy” mean?

I'm new in Differential Privacy (DP) and I have two questions: Why do we have the term differential in differential privacy? Are The local and global differential privacy and global and local ...
0
votes
2answers
48 views

privacy enhancing techniques on image data

To give some context: I am looking for a suite of techniques and tools that can theoretically enable me to conduct analysis such as classification on image datasets in a manner in which a naive ...
2
votes
3answers
167 views

Differential privacy on medical data

When we apply the differential privacy on medical data to protect the personal data of the patients, how the doctors can access the original data to analyze them and to intervene in real-time. In ...
0
votes
0answers
26 views

Mechanisms for Locally Private data release for continuous data

Most of the Local Differential Privacy mechanisms I've seen in the literature operate on discrete data, e.g. Randomized Response or RAPPOR. Can you point me to some LDP mechanisms for continuous data (...
2
votes
1answer
203 views

Interpretation of advanced composition theorem of differential privacy

In "The Algorithmic Foundations of Differential Privacy" book, Advanced Decomposition Theorem (Thm 3.20) is stated as follows: For all "$\epsilon, \delta, \delta' \geq 0$, the class of ($\...
1
vote
1answer
63 views

How is it possible to define differential privacy on two databases that differ more than a single entry?

The original definition of $\epsilon-$differential privacy is for two databases $D_1$, $D_2$ that differ at most one entry and an randomized algorithm $A$. We have a bound on the probability ratio $\...
3
votes
2answers
82 views

What's the meaning of probabilities in differential privacy formula?

I don't understand what does it mean by "The probability is taken is over the coin tosses of K." Does it mean, the probability distribution is generated based on exactly same data but only the ...
2
votes
0answers
48 views

Differential privacy RAPPOR article proof doubts

Recently I've been trying to understand the RAPPOR proof: \begin{eqnarray*} P(B' = b' | B = b^*) & = & \left(\frac{1}{2}f\right)^{b'_1}\left(1 - \frac{1}{2}f\right)^{1 - b'_1} \times \ldots \\...
3
votes
1answer
96 views

Why does ε-differential privacy protect the subset of 1/ε edges in terms of graphs?

In the book The Algorithmic Foundations of Differential Privacy by Cynthia Dwork, Aaron Roth on page 24, databases that take the form of graphs are discussed. We could on the other hand consider ...
0
votes
0answers
48 views

How to analyse the sensitivity in argmax in exponential mechanism of differential privacy?

Consider we have a database $D=[1,2,1,3]$, and the query for $\mathop{\arg\max}_{i} D_i$. So how to analyse the sentivity of the utility function? for the sensitivity of $u$ equals to $\Delta u=\max_{...
2
votes
2answers
877 views

Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive?

According to its mathematical definition, a random algorithm $M: D\rightarrow R$ satisfies $\epsilon$-differential privacy if the adjacent datasets $x, y \in D$ where $D$ is a whole dataset and ...
1
vote
1answer
241 views

what is the relationship between epsilon and sensitivity in the Differential-Privacy?

In some Differential-Privacy(DP) papers, they use epsilon as the x-axis in the figures of the experiments' result while other papers use the sensitivity. What is the relationship between epsilon and ...
2
votes
0answers
79 views

Differential privacy and Shamir's scheme

I have been unable to find any proofs (for my own reference) that demonstrate that Shamir's secret sharing scheme does (or does not) satisfy the definition of $\textbf{differential privacy}$ as ...
3
votes
1answer
112 views

Laplace Mechanism Proof: Why this product operator?

The equation below shows the proof of Laplace mechanism for differential privacy. I am not understanding the product operator, is this a common rule? $$ \frac{p_x(z)}{p_y(z)} = \prod_{i=1}^{k}\left(\...
1
vote
0answers
150 views

Laplace mechanism from Exponential mechanism in Differential Privacy

In McSherry and Talwar's paper which introduces the exponential mechanism for differential privacy, they say that the Laplace mechanism can be captured by choosing the score function as $q(d,r) = - |f(...
3
votes
1answer
475 views

Difference between ε-differential privacy and (ε, δ)-differential privacy

I don't understand the necessity of introducing the additive term δ in the differential privacy definition. Moreover, reading different papers and blogs they say that because of the δ term the ...
3
votes
1answer
396 views

Differential privacy of “randomized responses”

We define randomized responses as follows: In a question that can be responded with a "Yes" or "No", a respondent is asked to flip a fair coin, in secret, and answer the truth if it comes up tails. ...
3
votes
1answer
195 views

what does differential privacy (in machine learning) promise or guarantee?

I am recently reading some papers about privacy-preserving machine learning. Some works incorporate the idea of differential privacy to protect the privacy of the training dataset when the model is ...
4
votes
1answer
159 views

Differential privacy on multiple queries – what is the behavior?

Differential privacy framework still continue to be obscure in the following case: If I make a set of queries, I can join their output to restore the original data. For this issue we have composition ...
2
votes
2answers
80 views

Sensitivity of probability measure in differential privacy

I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. ...
4
votes
1answer
546 views

Parallel Composition of ($\epsilon, \delta$) differential privacy

I know that if there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $\epsilon_1, \cdots ,\epsilon_n$ differential privacy, ...
10
votes
1answer
502 views

Intuitive explanation of the $\varepsilon$ parameter in differential privacy

I think I have a decent intuitive understanding of what the $\delta$ parameter means in $(\varepsilon,\delta)$-differential privacy: I can explain it to a non-specialist in terms of "what are the ...
4
votes
1answer
756 views

Differential Privacy: why $\delta$ negligible on the row numbers?

The definition of differential privacy says that an algorithm $M$ is $(\epsilon,\delta)$-differentially private if $$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$ where $D,D'$ ...
3
votes
1answer
227 views

Differential privacy per record

Generally, differential privacy adds noise to a query result, such as a sum or an average, in an interactive way. Is there any way for implementing differential privacy such that noise will be added ...
2
votes
1answer
347 views

What is ε in differential privacy?

In ε-differential privacy, what does the ε refer to? Is it privacy value or the notation used? Can anyone provide an example of differential privacy?
3
votes
2answers
378 views

Differential Privacy and appropriate noise distribution

In differential privacy solutions and more specifically for queries that they do entail counting the proposed solutions define the Laplace distribution that is best calibrated for low error. Other ...
3
votes
2answers
391 views

Differential privacy definition

Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between ...
7
votes
3answers
632 views

Are there any differences between PIR, oblivious transfer and differential privacy?

I am trying to make a taxonomy of the different purposes of some cryptographic protocols. Generally speaking, the purpose of PIR, oblivious transfer and differential privacy--it sounds as if they were ...