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
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 ...
Glock K's user avatar
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. ...
Amirhossein Adavoudi's user avatar
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 ...
travelingbones's user avatar
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 ...
Amirhossein Adavoudi's user avatar
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 ...
Amirhossein Adavoudi's user avatar
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. ...
Amirhossein Adavoudi's user avatar
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 ...
a.t.'s user avatar
  • 101
0 votes
0 answers
43 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-$...
Amirhossein Adavoudi's user avatar
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 ...
Amirhossein Adavoudi's user avatar
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 $...
Amirhossein Adavoudi's user avatar
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 ...
Genie's user avatar
  • 83
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 ...
A J's user avatar
  • 13
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}_{...
Ekene E.'s user avatar
  • 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\...
Quaxton Hale's user avatar
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 ...
user167622's user avatar
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 ...
Sumana bagchi's user avatar
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 ...
KRWTS's user avatar
  • 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 ...
batman's user avatar
  • 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 ...
Karup's user avatar
  • 71
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 ...
user60588's user avatar
  • 191
2 votes
1 answer
144 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 ...
xavi's user avatar
  • 121
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 $\...
umityigitbsrn's user avatar
2 votes
1 answer
95 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 ...
independentvariable's user avatar
2 votes
1 answer
198 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, ...
Sahil's user avatar
  • 23
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, ...
Mir Henglin's user avatar
2 votes
1 answer
195 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 ...
independentvariable's user avatar
3 votes
1 answer
370 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? ...
SpiderRico's user avatar
2 votes
2 answers
123 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 ...
Tiana Johnson's user avatar
2 votes
0 answers
49 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: ...
George Li's user avatar
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) ...
Amit Portnoy's user avatar
1 vote
1 answer
789 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 < ...
independentvariable's user avatar
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 ...
N J's user avatar
  • 101
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{...
John Doe's user avatar
  • 155
2 votes
1 answer
60 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 ...
Miguel Gutierrez's user avatar
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 ...
Proy's user avatar
  • 153
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: ...
partyTuringFriend's user avatar
2 votes
1 answer
48 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 ...
Proy's user avatar
  • 153
3 votes
1 answer
628 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....
Proy's user avatar
  • 153
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 ...
hharcolezi's user avatar
2 votes
1 answer
92 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" ...
Mark Schultz-Wu's user avatar
2 votes
1 answer
106 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 ...
ABHS's user avatar
  • 23
2 votes
1 answer
60 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 ...
hello world's user avatar
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)...
John Doe's user avatar
  • 155
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 ...
Ziva's user avatar
  • 235
6 votes
1 answer
651 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 (...
Ted's user avatar
  • 1,008
2 votes
0 answers
248 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)|\...
Ted's user avatar
  • 1,008
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 ...
Ted's user avatar
  • 1,008
2 votes
1 answer
136 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\...
Piggy Wenzhou's user avatar
1 vote
1 answer
624 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 ...
redplanet's user avatar
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 ...
Joe Zhou's user avatar
  • 111