0
$\begingroup$

From The Algorithmic Foundations of Differential Privacy It wrote that :

enter image description here

But from this pdf

enter image description here

I am confused which one is right, or I misunderstand.

In second method, after I compute Pr[v], and then what to do?

I am not sure how to implement the Laplace mechanism.

$\endgroup$
2
$\begingroup$

These two formulas are the same thing. The second formula is the probability density function of the Laplace distribution centered on 0 ($\mu=0$) — although rather than $Pr[v]$, the second PDF should probably have used a notation like $f(v)$ to make it clear that this is a probability density function and not the probability of returning exactly $v$.

If the question about "how to implement the Laplace mechanism" was referring to something you want to do in practice, then you probably don't want to do it yourself; but you want to use an implementation safe against floating-point attacks. Here's an example of open-source software you can use (disclaimer: I'm part of the team behind that library).

| improve this answer | |
$\endgroup$
0
$\begingroup$

If I would see both I would have the same misunderstanding you had. I got a little late but in order to connect ideas we have $v = x$ where $v \in Y_i$ and $\mathcal{M}_L = f(x)+v$. What I see here is a bad notation on the last one, since $v$ is a point, not a distribution as $Y_i$. This should be something like $V_i \sim Lap(\Delta f / \epsilon)$ where you want to know $Pr[V=v]$.

Then I always going to prefer the full notation of Laplace and function which is $Lap(\mu,b)$ which has a mean of $\mu$ and a variance of $2b$. Now the probability of $x$ in Laplace is $Lap(x \mid (\mu,b))$.

$$Lap(x \mid (\mu,b))=\frac{1}{2b}e^{\frac{-|x-\mu|}{b}}$$

What you want to compute is the $f(x)$ with the noise. If you only are going to compute the noise then you should use only $Pr[v]=Pr[Y=x]$ (Remember $x=v$). What you want to compute is $\mathcal{M}_L(x)$. Which by definition (now this is why is useful the mean notation) is :

$$\mathcal{M}_L(x \mid (\mu,b))=\frac{1}{2b}e^{\frac{-\varepsilon|x-f(x)|}{\Delta f}}$$

Because you only move the distribution to the left by $f(x)$. Then you have :enter image description here

If you want to implement the mechanism you can obtain the query $f(x)$ from a Database and using a library that has Laplace distribution do $\mathcal{M}_L(x) = f(x)+ Y_i$ where $Y_i \sim Lap(\Delta f / \epsilon)$. Remember $x$ is the database and $f(x) \in \mathbb{R}^k$

| 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.