People who code: we want your input. Take the Survey

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
13
votes
1answer
757 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 ...
7
votes
3answers
700 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 ...
6
votes
2answers
200 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 ...
5
votes
1answer
861 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 ...
5
votes
1answer
231 views

Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity

Suppose you have a function $f$ that takes a dataset $D$ as input and returns an output in $\mathbb{R}^d$. If this function has $L^2$-sensitivity $\Delta$, then the analytical Gaussian mechanism (...
5
votes
0answers
81 views

Amazon's anti-piracy: how many movies can $m$ conspirators leak?

Is there any existing academic literature about this application of traitor tracing? A video streaming service has a new anti-piracy technique to identify customers who capture and share their ...
4
votes
1answer
1k 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'$ ...
4
votes
1answer
276 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 ...
4
votes
1answer
214 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 ...
4
votes
1answer
751 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, ...
3
votes
2answers
100 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 ...
3
votes
1answer
616 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
81 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,...
3
votes
2answers
615 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 ...
3
votes
1answer
117 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 ...
3
votes
1answer
250 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 ...
3
votes
1answer
89 views

Laplace Inequality

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then: $$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$. I know that for $r*>0$ it satisfies ...
3
votes
1answer
137 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(\...
3
votes
2answers
600 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
489 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 ...
3
votes
1answer
75 views

Calculating differentially private average of a dataset

I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the following algorithm presented in Li et al. (2016): Proposition 2....
2
votes
2answers
1k 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 ...
2
votes
3answers
270 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 ...
2
votes
1answer
34 views

Can Differential Privacy be used to show that two distributions are indistinguishable?

Differential privacy can be used to show that the "privacy loss" of a certain computation is "bounded" in a meaningful way. In cryptography, often "indistinguishability" ...
2
votes
1answer
68 views

Differential Privacy: is the bound for group privacy tight?

Suppose mechanism $M$ is $(\epsilon, \delta)$-differentially private. For datasets $x$ and $x''$ that differ by 2 elements, we have $$ Pr[M(x)=y] \le e^{\epsilon} Pr[M(x')=y] + \delta \le e^{2\...
2
votes
1answer
216 views

$(\epsilon, \delta)$-differential privacy: main motivation of $\delta$

I am wondering why (not how) we relax $\epsilon$-differential privacy to $(\epsilon, \delta)$-differential privacy. Is the main motivation to reduce the variance of the noise added to the query with a ...
2
votes
1answer
377 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?
2
votes
1answer
51 views

The sensitivity in differential privacy with deep learning

In differentially private deep learning, the sensitivity is determined by clipping gradient norm (see Abadi et al.'s paper). In this paper, when the clipping gradient norm is $C$, the sensitivity is $...
2
votes
1answer
129 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 '...
2
votes
1answer
89 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 ...
2
votes
1answer
63 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 ...
2
votes
0answers
178 views

Generic result on the guarantees of using two differentially private noise mechanisms one after the other

Let $f$ be a function that takes a database $D$ as input and returns a real number. Assume that $f$ has sensitivity 1: for any databases $D_1$ and $D_2$ differing in a single record, $|f(D_1)-f(D_2)|\...
2
votes
1answer
79 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
0answers
54 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 \\...
2
votes
0answers
87 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 ...
2
votes
2answers
129 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. ...
1
vote
2answers
164 views

Differential privacy noise that scales with $L_p$-sensitivity with $p>2$?

It is well-known that to make the result of a $\mathbb{R}^d$-valued query $(\varepsilon,\delta)$-differentially private, you can add noise to it. If you add Laplace noise, you need to scale the noise ...
1
vote
1answer
80 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 $\...
1
vote
1answer
301 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 ...
1
vote
1answer
67 views

Multiple attributes under shuffled differential privacy

Notation: eps_c (epsilon central), eps_l (epsilon local), n (number of users), d (number of attributes). A single attribute A_i may have |A_i|=r different values for i in [1,d]. Let's suppose each ...
1
vote
1answer
65 views

Differential privacy what does “where the probability is taken over the randomness used by the algorithm” mean?

The definition of differential privacy is as follows: A randomized mechanism $\mathcal{M}$ is $(\epsilon, \delta)$-differentially private, where $\epsilon \leq 0$ and $\delta \leq 0$, if for any ...
1
vote
1answer
69 views

Sensitivity on differential privacy

I want to verify my knowledge of sensitivity. So in $\epsilon$-differential privacy, the noise is added with the Laplace mechanism depending on the sensitivity and the privacy loss parameter. Laplace ...
1
vote
1answer
86 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)$-...
1
vote
1answer
75 views

How can we define $\epsilon$-differential privacy for non-deterministic algorithms?

We know that non-trival deterministic algorithm does not guarantee privacy and randomization is essential for privacy (pp.16 in [Dwork and Roth 2014] ). The well-known $\epsilon$-diferential privacy ...
1
vote
1answer
81 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 ...
1
vote
0answers
14 views

Does subsampling amplify privacy budget of differentially private median function

I was reading that subsampling amplifies the privacy budget. I understand that it reduces the contribution of data to the aggregation function. I am wondering how sub-sampling impacts the median ...
1
vote
1answer
49 views

How to adapt the equation of Gaussian mechanism noise based on number of executions

I'm trying to build a differentially private machine learning model. I'm using the Gaussian mechanism to calculate the required noise amount based on pre-defined privacy budget value 𝜖 The equation ...
1
vote
1answer
23 views

Selection of the noise application position in differential privacy

In DP-SGD proposed by M Abadi in 2016, noise is applied to the gradient, so every round of training needs to be applied. My questions are: Can I choose to apply noise that meets the DP requirements to ...
1
vote
1answer
115 views

Advanced Composition (Differential Privacy)

I have a problem understanding the proof of the corollary of Advanced Composition Theorem Advanced Composition: For all $\varepsilon,\delta,\delta' \geq 0$ the class of $(\varepsilon,\delta)$-...
1
vote
1answer
47 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$ ...