Differential Privacy of the Laplace mechanism with non-deterministic function

Question

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 private, use deterministic functions as the query f that is made on the database (e.g. counting queries).

But is the statement actually only valid for deterministic f?

Seems to me, that adding Laplace noise is a popular easy way to make any kind of query differentially private. Imagine having a random query, but its randomness is weird and you just say: Eh, skip finding out, if the mechanism is private on its own. Just add additional noise (in this case laplace noise) and it will be fine. Judging from the idea behind adding noise to improve privacy this should be possible - I thought.

If the laplace mechanism works for non-deterministic functions as well - where in the proof of the differential privacy is the influence of the function's randomness taken into account? If the standard proof as shown below (from "The algorithmic foundations of differential privacy" by Dwork/Roth) doesn't work for random f - is there a way to prove it in another way? How?

Thank you in advance for any help.

Answer 1

The Laplace mechanism only works for deterministic $f$, because the notion of "sensitivity" (the $\Delta f$ in the formulas above) isn't well-defined for random functions. $\Delta f$ is the maximum difference between $f(x)$ and $f(y)$, for neighboring $x$ and $f$. If $f$ is a random function, then that notion of "difference" becomes much more complicated to capture, so in general, you simply assume that $f$ is deterministic.

To extend this to the case where $f$ is random, you could define $\Delta f$ to be the maximum difference between a possible output of $f(x)$ and a possible output of $f(y)$, for all possible values of the random bits used by $f$. That would still allow you to say $\frac{||f(x)-f(y)||}{\Delta f}\le1$. But that doesn't work if that value is unbounded (for example, if $f$ implicitly adds Gaussian noise to the result of the computation), and that's a loose approximation in general; so it's pretty much never done.