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.
94
questions
1
vote
2
answers
279
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
1
vote
2
answers
48
views
In order to achieve differentially private machine learning can one simply apply the Laplace mechanism after an SGD scheme? If so does it work well?
Consider a standard supervised machine learning problem on private data. Instead of using DPSGD, suppose that one uses a non-private SGD scheme to produce optimal model parameters $\theta$ (done in ...
- 123
1
vote
1
answer
211
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
1
vote
1
answer
120
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,605
1
vote
2
answers
602
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 ...
- 11
1
vote
1
answer
176
views
Relating the noisy data to it's associated original/actual one
We have a set of query answers, i.e., $A = \{A_1, A_2, \dots, A_m\}$ and then we add noise to each of $A_i$ using a mechanism ($M$) providing differential privacy, i.e., $M(A_i) = O_i$. We denote the ...
1
vote
1
answer
792
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 < ...
1
vote
1
answer
342
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{...
- 155
1
vote
1
answer
98
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
1
vote
1
answer
627
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
96
views
Why an adversary can guess a secret while we have provided differential privacy?
Let's consider a scenario with $k$-secrets, each associated with a user. Every user aims to obscure their respective secret using a $d$-privacy method.
We say a user uses $d$-privacy within a radius $...
1
vote
2
answers
103
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 ...
- 13
1
vote
2
answers
85
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 $\...
1
vote
1
answer
60
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:
...
1
vote
1
answer
166
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
vote
1
answer
255
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 ...
- 11
1
vote
2
answers
68
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 ...
- 93
1
vote
0
answers
155
views
How to achieve $d-$privacy considering some secrets?
We have a set of secrets $S = \{x_1, x_2, \dots, x_n\}$ known to an adversary. Each $x_i \in S$ belongs to user $u_i$ who needs to obfuscate his secret using the notion of $d-$privacy defined in the ...
1
vote
0
answers
44
views
Server parameters for Differential Zero Knowledge?
I'm working to use Differential Zero Knowledge proof on client local data before sharing with server. May I know which parameters need to be established at server side as to verify that the client is ...
- 83
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
1
vote
0
answers
207
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(...
- 11
0
votes
2
answers
319
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 ...
- 47
0
votes
2
answers
501
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 $\...
- 101
0
votes
1
answer
101
views
Privacy-loss of an individual due their associated records
We utilize a differential privacy mechanism (Laplace noise, with scale $b$) to provide the privacy of records stored within a dataset. Each individual is associated with two, and at most $k$, records. ...
0
votes
1
answer
38
views
If the truncation function provides differential privacy
We have values in the range $[a, b]$, and we apply a differential privacy mechanism to add noise to these values. After obtaining the noisy values, we employ the following truncation function: if a ...
0
votes
1
answer
135
views
"Select" query that provides differential privacy
We possess a database containing entries, where each entry consists of a person's ID and the corresponding fractional number $w$ (e.g., 2.34, 3.4, 12.3 etc) falling within the range of 1.00 to 100.00. ...
0
votes
1
answer
50
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 ...
- 191
0
votes
1
answer
71
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
0
votes
1
answer
59
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
0
votes
2
answers
87
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)...
- 155
0
votes
1
answer
278
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 ...
0
votes
1
answer
244
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 ...
- 93
0
votes
0
answers
17
views
Differential Privacy: when the tokenizer is related to the dataset
So I want to train a model with DP-SGD. However, I noticed that by how my input dataset is constructed, the tokenizer is actually related to the input data. (e.g., picking out a sample may affect how ...
- 1
0
votes
0
answers
52
views
Privacy Challenges in Applying Fully Homomorphic Encryption to Find Closest Shops Based on Zipcodes
Context
To learn about fully homomorphic encryption (FHE) and a new language I implemented the Paillier cryptosystem in Go, and I thought it would be fun to apply it to the following interaction:
A ...
- 101
0
votes
0
answers
44
views
Is it possible to consider a mechanism without adding noise to provide differential privacy?
We have a set of secrets $S = \{x_1, x_2, \dots, x_n\}$ known to an adversary. Each $x_i \in S$ belongs to user $u_i$ who needs to obfuscate his secret, i.e. $K(x_i) = o_i$, using the notion of $d-$...
0
votes
0
answers
29
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}_{...
- 101
0
votes
0
answers
35
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
15
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
47
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
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
0
votes
0
answers
50
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
0
answers
134
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
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 ...
