Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [differential-privacy]

The tag has no usage guidance.

1
vote
1answer
35 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 ...
2
votes
1answer
43 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. ...
2
votes
1answer
123 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 ...
0
votes
0answers
20 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_{...
1
vote
2answers
108 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
2answers
263 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
2answers
181 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
1answer
82 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 ...
1
vote
1answer
60 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 ...
10
votes
1answer
327 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 ...
1
vote
0answers
51 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
69 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
105 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(...
0
votes
0answers
22 views

Randomized response with more than 2 options

It is well-known that the binary randomized response mechanism is differentially private, with $\varepsilon=ln(3)$ if each person answers truthfully with probability $0.5$, and uniformly randomly ...
3
votes
1answer
213 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
171 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. ...
2
votes
1answer
350 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, ...
4
votes
1answer
375 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
153 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
232 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?