Accés ràpid intranet

Més informació...

a a a
Inici

Report de recerca: DEIM-RR-12-002


Títol

Optimal Data-Independent Noise for Differential Privacy

Autor/s

Jordi Soria-Comas and Josep Domingo-Ferrer

Data

07-03-2012

Grup de recerca

CRISES - Criptografia i Secret Estadstic

Tipus de report

Recerca

Idioma

English

Nombre de pàgines

25

Resum

Differential privacy is a property that seeks to characterize privacy in data sets. It is formulated as a query-response method, and computationally achieved by output perturbation. Several noise-addition methods to implement such output perturbation have been proposed in the literature. We focus on data-independent noise, that is, noise whose distribution is constant across data sets. Our goal is to find the optimal data-independent noise distribution to achieve differential privacy. We propose a general optimality criterion based on the concentration of the probability mass of the noise distribution around zero, and we show that any noise optimal under this criterion must be optimal under any other sensible criterion. We also show that the Laplace distribution, commonly used for noise in differential privacy, is not optimal, and we build the optimal data-independent noise distribution. We compare the Laplace and the optimal data-independent noise distributions. For univariate query functions, both introduce a similar level of distortion; for multivariate query functions, optimal data-independent noise offers better responses with better data quality.

Paraules Clau

Data privacy, Differential privacy, Noise addition, Privacy-preserving data mining, Statistical disclosure control