1
$\begingroup$

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.

definition of the laplace mechanism proof of the laplace mechanism being differentially private

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\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.