Ehab ElSalamouny

Ehab ElSalamouny, Catuscia Palamidessi

The iterative Bayesian update (IBU) and the matrix inversion (INV) are the main methods to retrieve the original distribution from noisy data resulting from the application of privacy protection mechanisms. We show that the theoretical foundations of the IBU established in the literature are flawed, as they rely on an assumption that in general is not satisfied in typical real datasets. We then fix the theory of the IBU, by providing a general convergence result for the underlying Expectation-Maximization method. Our framework does not rely on the above assumption, and also covers a more general local privacy model. Finally we evaluate the precision of the IBU on data sanitized with the Geometric, $k$-RR, and RAPPOR mechanisms, and we show that it outperforms INV in the first case, while it is comparable to INV in the other two cases.

Ehab ElSalamouny, Sébastien Gambs

Users of location-based services (LBSs) are highly vulnerable to privacy risks since they need to disclose, at least partially, their locations to benefit from these services. One possibility to limit these risks is to obfuscate the location of a user by adding random noise drawn from a noise function. In this paper, we require the noise functions to satisfy a generic location privacy notion called $\ell$-privacy, which makes the position of the user in a given region $\mathcal{X}$ relatively indistinguishable from other points in $\mathcal{X}$. We also aim at minimizing the loss in the service utility due to such obfuscation. While existing optimization frameworks regard the region $\mathcal{X}$ restrictively as a finite set of points, we consider the more realistic case in which the region is rather continuous with a non-zero area. In this situation, we demonstrate that circular noise functions are enough to satisfy $\ell$-privacy on $\mathcal{X}$ and equivalently on the entire space without any penalty in the utility. Afterwards, we describe a large parametric space of noise functions that satisfy $\ell$-privacy on $\mathcal{X}$, and show that this space has always an optimal member, regardless of $\ell$ and $\mathcal{X}$. We also investigate the recent notion of $ε$-geo-indistinguishability as an instance of $\ell$-privacy, and prove in this case that with respect to any increasing loss function, the planar Laplace noise function is optimal for any region having a nonzero area.