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.
84
questions
1
vote
2
answers
82
views
Definition of Differential Privacy
Can someone please explain the definition of differential privacy. Here is the one which I see and am unable to understand it:
Its from this paper. I do not understand the use of $S$ here and also ...
- 11
0
votes
0
answers
27
views
Nature of differentially private Laplace mechanisms
In the Wikipedia page on differential privacy, the section on $\varepsilon$-differential privacy for the Laplace mechanism says that the Laplace mechanism is specified for some output as $\mathcal{T}_{...
- 1
0
votes
0
answers
32
views
Definition of $\left(\epsilon,\delta,\gamma\right)$-Random Differential Privacy
$\left(\epsilon,\delta,\gamma\right)$-Random Differential Privacy as defined in rubenstein17:
$$\begin{align*}Pr\left[\forall S \subset \mathbb{R}, Pr\left(A(D) \in S\right) \leq e^{\epsilon} \cdot Pr\...
- 101
0
votes
0
answers
9
views
Lower bound on additive error when releasing vector of values differentially privately
I have a vector of $n$ elements where each entry is a non-negative integer. Neighboring vectors differ in one element where the absolute value difference between the elements that differ is $1$. I ...
0
votes
0
answers
12
views
Partition/Range wise privacy
Consider two data streams $a_1,\cdots, a_n \in [a_{min}, a_{max}]$ and $b_1,\cdots, b_n \in [b_{min}, b_{max}]$, Such that $[a_{min}, a_{max}]$ and $[b_{min}, b_{max}]$ do not overlap.
A Differential ...
0
votes
1
answer
38
views
Utility Guarantee of Small Data Base Mechanism in Differential Privacy
I am reading Section 4.1 (An offline algorithm: SmallDB) of The Algorithmic Foundations of Differential Privacy by Dwork and Roth. I am stuck at the proof of Proposition 4.4, which is about the ...
- 101
1
vote
0
answers
32
views
Introducing differential privacy in two different ways
I would like to investigate if it is possible to introduce Differential Privacy (DP) to a model via both adding Laplacian noise to the training data and then training with DP-SGD updates. Is it a ...
- 11
2
votes
0
answers
113
views
Protecting value decomposition risk in microdata release
Consider a scenario where a company wants to release a microdata of their employees total annual compensation for the following year to an analyst in a recruiting firm in order to provide an ...
- 71
0
votes
1
answer
45
views
SMCQL practical examples
I am looking for some practical examples on how to use SMCQL on some typical SQL queries. The paper seems to be oriented more towards theory. Can somebody point me to some examples to understand it ...
- 181
0
votes
0
answers
36
views
A Method to Preserve Gradient Privacy in Federated Learning
In the federated learning architecture, there are two methods of gradient privacy protection: differential privacy and homomorphic encryption. What are the advantages and disadvantages of these two ...
- 41
2
votes
1
answer
101
views
Apply local differential privacy to a datasets
How to apply local differential privacy to specific categorical values in order to perform some analysis? Does there exist a tool?
For example, I have the following ...
- 121
1
vote
2
answers
77
views
Why the set membership symbol (∈) is used in formal differential privacy definition?
In The Algorithmic Foundations of Differential Privacy (Dwork, C; Roth, A), the formal definition of differential privacy is given as:
"
The randomized algorithm $\mathcal{M}$ with domain $\...
2
votes
1
answer
86
views
Approximate differential privacy: avoiding composition in vector-queries
Assume we have an $n$-dimensional real-valued function $f$ whose $\ell_1$ sensitivity is equal to $GS(f) = 1$. We can also assume the sensitivity of each dimension is also $\Delta f = 1$.
For pure ...
2
votes
1
answer
188
views
Differential privacy with strong composition under k-mechanisms with different (ε, δ)-DP bounds
The overall DP under the strong composition theorem for k-mechanisms is ($\epsilon \sqrt{k log(1/\delta)}$, k$\delta$) such that each individual mechanism has ($\epsilon, \delta$)-DP.
But what if say, ...
- 23
0
votes
1
answer
61
views
When can composition be viewed as a vector-valued query with differential privacy?
Page 33 of The Algorithmic Foundations of Differential Privacy gives two examples where a composition of mechanisms can be viewed as a vector-values output, histograms, and fixed counting queries, ...
- 103
2
votes
1
answer
157
views
Advanced Composition in DP is worse than Basic Composition
I have problems with understanding the advanced composition theorem in DP.
Let I have two approximate-DP mechanisms ($k = 2)$ where each satisfies $(\epsilon = 0.5, \delta = 0.1)$-DP. By basic ...
3
votes
1
answer
254
views
How do we select values for parameters when using Differential Privacy?
I'm aware we can quantify privacy with ε-differential privacy (ε-DP). But when we apply DP, how do we actually select the value for ε ? Are there some rule-of-thumbs? Is it decided case-by-case basis? ...
- 441
2
votes
2
answers
109
views
Differential Privacy with Outliers
To use the Laplace mechanism, we have to get the global sensitivity of a query function. What do we do in the case where there is one huge outlier(or multiple outliers) in the dataset such that the ...
2
votes
0
answers
47
views
Proof of Basic Composition in Differential Privacy
I'm currently reading the proof of basic composition from the paper https://link.springer.com/content/pdf/10.1007/11761679_29.pdf. In particular, Theorem 1 in Section 2.2.
The proof starts as follows:
...
- 21
0
votes
0
answers
34
views
differential privacy over a normal vector
We're given a vector $x\in \mathbb{R}^d$ whose coordinates where sampled from a known normal distribution $\mathcal{N}(0, \sigma^2)$.
How should I send this vector while maintaining (local) ...
- 101
1
vote
1
answer
617
views
Differential Privacy: Gaussian Mechanism when $\epsilon >1$, Laplace Mechanism when $\epsilon = 0$
In Differential Privacy resources, the limiting cases of $\epsilon, \delta$ are not justified well enough.
For example, on Wikipedia, it is said that Gaussian mechanism only works when $\epsilon < ...
0
votes
0
answers
49
views
Revealing percentiles of an ordered dataset without revealing its size
Given an ordered set $S$ of positive integers (eg. $S=\{503, 503, 520, 551...N\}$) I want to be able to reveal the percentile rank (eg. 503 is in the top 10th percentile) for each element of a ...
- 101
0
votes
1
answer
289
views
Is privacy loss a random variable?
The "standard" book (Dwork & Roth, 2014) defines Privacy loss as follows (p. 18)
The quantity
$$
\mathcal{L}^{(\xi)}_{\mathcal{M}(x) || \mathcal{M}(y)} = \ln \left(
\frac{\Pr[\mathcal{...
- 145
2
votes
1
answer
48
views
Sensitivy Maximization RAPPOR (Local Differential Privacy)
Hi I have a doubt at the end of the proof of the RAPPOR Algorithm, when they say the sensitivity is maximized when $b'_{h+1}=b'_{h+2}=...=b'_{2h}=1$ and $b'_{1}=b'_{2}=...=b'_{h}=0$. I don't ...
- 152
0
votes
1
answer
53
views
How to set additive noise for amplification by subsampling
I am testing a privacy mechanism and implementing privacy amplification by subsampling. I am calculating the count aggregate function where the number of participants is known. I am applying a Laplace ...
- 153
1
vote
1
answer
59
views
Proving differential privacy for any real number epsilon?
I have to prove some differential privacy in a exercise i'm doing.
I have this table, and problem description:
...
2
votes
1
answer
42
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 ...
- 153
3
votes
1
answer
547
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....
- 153
1
vote
1
answer
96
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 ...
- 13
2
votes
1
answer
80
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" ...
- 11.6k
2
votes
1
answer
102
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 ...
- 23
2
votes
1
answer
57
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 ...
- 31
0
votes
2
answers
77
views
Query sensitivity of time series under differential privacy
I stumbled upon a paper that proposes local DP around this argument:
A user $u_i$ generates a sequence $s_{i}$ of observations at certain timestamps:
$$
s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n)...
- 145
1
vote
1
answer
195
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 ...
- 235
6
votes
1
answer
613
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 (...
- 1,008
2
votes
0
answers
246
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)|\...
- 1,008
1
vote
2
answers
256
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,008
2
votes
1
answer
123
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\...
- 173
1
vote
1
answer
489
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 ...
- 93
1
vote
1
answer
144
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 ...
- 111
-1
votes
1
answer
125
views
Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations
So I am looking for an explanation of an experiment.
In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that ...
2
votes
1
answer
107
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 $...
- 21
3
votes
1
answer
103
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 ...
- 152
2
votes
1
answer
738
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
1
answer
417
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)$-...
- 152
3
votes
1
answer
185
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,...
- 152
2
votes
1
answer
405
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 ...
- 21
3
votes
1
answer
201
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
1
answer
96
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$ ...
- 145
2
votes
2
answers
863
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)$-...
- 21