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
0 votes
0 answers
35 views

How to quantify privacy, when using homomorphic encryption?

How can you measure how secure or private the new variables are relative to the real (actual) variables. I want to compare homomorphic encryption and differential privacy in combination with machine ...
user avatar
  • 1
0 votes
1 answer
34 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, ...
user avatar
0 votes
0 answers
38 views

Compute Differential Privacy level for any randomised algorithm

I have recently started learning differential privacy for my BTech project. I understand that it adds noise to the input stream based on a privacy level (say $\epsilon$) and a query function (say $f$),...
user avatar
1 vote
1 answer
52 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 ...
user avatar
3 votes
1 answer
77 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? ...
user avatar
1 vote
1 answer
51 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 ...
user avatar
1 vote
0 answers
31 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: ...
user avatar
0 votes
0 answers
32 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) ...
user avatar
1 vote
1 answer
111 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 < ...
user avatar
0 votes
0 answers
43 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 ...
user avatar
  • 101
0 votes
1 answer
91 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{...
user avatar
  • 145
1 vote
1 answer
20 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 ...
user avatar
0 votes
1 answer
40 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 ...
user avatar
  • 153
0 votes
1 answer
39 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: ...
user avatar
2 votes
1 answer
26 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 ...
user avatar
  • 153
3 votes
1 answer
115 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....
user avatar
  • 153
1 vote
1 answer
81 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 ...
user avatar
2 votes
1 answer
41 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" ...
user avatar
  • 8,424
2 votes
1 answer
73 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 ...
user avatar
  • 23
1 vote
1 answer
34 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 ...
user avatar
0 votes
2 answers
63 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)...
user avatar
  • 145
1 vote
1 answer
112 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 ...
user avatar
  • 235
6 votes
1 answer
383 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 (...
user avatar
  • 968
2 votes
0 answers
212 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)|\...
user avatar
  • 968
1 vote
2 answers
197 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 ...
user avatar
  • 968
2 votes
1 answer
86 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\...
user avatar
1 vote
1 answer
148 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 ...
user avatar
1 vote
1 answer
94 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 ...
user avatar
  • 111
-1 votes
1 answer
114 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 ...
user avatar
2 votes
1 answer
59 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 $...
user avatar
  • 21
3 votes
1 answer
101 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 ...
user avatar
2 votes
1 answer
383 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 ...
user avatar
1 vote
1 answer
203 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)$-...
user avatar
3 votes
1 answer
144 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,...
user avatar
2 votes
1 answer
176 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 ...
user avatar
2 votes
1 answer
149 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 '...
user avatar
2 votes
1 answer
74 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$ ...
user avatar
  • 145
1 vote
1 answer
195 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)$-...
user avatar
1 vote
1 answer
108 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 ...
user avatar
  • 11
0 votes
2 answers
154 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 ...
user avatar
  • 37
2 votes
1 answer
105 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 ...
user avatar
  • 145
0 votes
2 answers
129 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 $\...
user avatar
  • 101
0 votes
1 answer
155 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 ...
user avatar
2 votes
1 answer
83 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 ...
user avatar
0 votes
1 answer
133 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 ...
user avatar
6 votes
2 answers
218 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 ...
user avatar
0 votes
2 answers
57 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 ...
user avatar
  • 83
2 votes
3 answers
282 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 ...
user avatar
3 votes
2 answers
907 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 ...
user avatar
1 vote
1 answer
99 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 $\...
user avatar
  • 1,495