3
$\begingroup$

The Laplace mechanism is a standard way of making the output of a function $f$ differentially private. More concretely, let $\Delta_f$ be the sensitivity of $f$, i.e. the maximum value by which the output of $f$ can change, if the input database is changed by one row. On input database $x$, the $\epsilon$-private Laplace mechanism outputs $x + R$, where $R$ is sampled from the $Lap(1/\epsilon)$ distribution, which is scaled by $1/\epsilon$. Since the distribution is symmetrically distributed around $0$, it can regularly happen that the added noise $R$ is negative and thus the reported value $x + R < x$.

Question: Are there mechanisms that only adds positive noise, i.e. that never produces an output that is smaller than the real output? Importantly, I'm interested in mechanisms that do not know a lower bound on the output range of $x$ (this exclude simple truncation approaches like the ones used for histograms, which can be truncated at $0$).

$\endgroup$

1 Answer 1

1
$\begingroup$

what you are looking for is the "exponential mechanism". See https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf. It is a very general mechanism, which includes one-sided noise as a special case.

$\endgroup$
2
  • $\begingroup$ Hi, could you elaborate further? I'm not familiar with the topic, but I want to be sure the answer is not erroneous. In section 3.4 paragraph 2, I seem to read the opposite "The exponential mechanism was designed for situations in which we wish to choose the “best” response but adding noise directly to the computed quantity can completely destroy its value, such as setting a price in an auction, where the goal is to maximize revenue, and adding a small amount of positive noise to the optimal price (in order to protect the privacy of a bid) could dramatically reduce the resulting revenue." $\endgroup$ Feb 1 at 9:08
  • 1
    $\begingroup$ The exponential mechanism is very general and can be specified in multiple ways for different purposes. One possible specification is the one in Example 3.5: the auction you refer to. But a very different specification is one-sided noise (only positive or only negative Laplace distribution), as used in Example 3.6 and Theorem 3.13. $\endgroup$ Feb 2 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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