5
$\begingroup$

I am learning differential privacy now, and there is no one surrounding I can ask questions about differential privacy. I am confused about the definitions of the global sensitivity and local sensitivity. enter image description here

enter image description here

The two definitions are from the book 《Differential Privacy and Applications》written by Tianqing Zhu, Gang Li, Wanlei Zhou, Philip S. Yu.

My understanding is:

The neighbor database only has one different record to the original database.

For the definition of global sensitivity, if $f=\sum x_i$, $x_i\in \{0,1\}$, the global sensitivity is the max value of $\sum |f(D)-f(D')|, D'\in D^n-D$, and there is only one different record between neighbor databases, so it equals to the max value among $|f(D)-f(D')|$, is obvious 1.

I am not if my understanding is right.

And how to understand local sensitivity?

$\endgroup$
5
$\begingroup$

I have read the reference to the definition in Zhu's book. The paper is 《Smooth Sensitivity and Sampling in Private Data Analysis》, which gives more distinct definitons of global sensitivity and local sensitivity[1].

enter image description here

enter image description here

Obviously, $GS_f=max_{x}LS_f(x)$

[1] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC 07, 2007.

$\endgroup$
0
$\begingroup$

Global Sensitivity (GS) depends only on the function f. When trying to figure out the GS of function f, we examine all possible pairs of neighboring datasets in the domain of the function f.

Local Sensitivity (LS) depends on both the function f and the data set at hand D (known as an instance). When trying to figure out the LS of (f, D), we only examine a subset of all possible pairs of neighboring datasets, holding one of the dataset constant at D.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.