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 mechanism as shown below:

DP-count = True count + Laplace ($\frac{\Delta}{\epsilon}$)

The sensitivity depends on the population size. For population size, N the sensitivity, $\Delta = \frac{1}{N}$. If I apply the subsampling mechanism will it impact the sensitivity? For m samples, should I set sensitivity $\Delta = \frac{1}{m}$? Should I keep $\epsilon$ same as before for comparison purpose?


Let $M$ be a mechanism with $O(\epsilon)$ differential privacy and $D$ be the database. To apply privacy amplification by sampling, define a another database $D'$ by selecting each member of $D$ with probability $p$, then apply $M$ to $D'$. The overall privacy of this procedure is $O(p\epsilon)$. For the exact expression hidden in the big $O$ notation, see Lemma 2 https://www.cs.bgu.ac.il/~beimel/Papers/BKN.pdf.

If $M$ is defined only for fixed-sized databases, then obviously you can't apply it to $D'$. If on the other hand, if $M$ is defined for arbitrary-sized databases, to use the Laplace mechanism, the sensitivity of your function must be independent of the input (per the definition of sensitivity). So the statement that the sensitivity of the function $f$ is $1/N$ doesn't make sense.


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.