Paper 2014/982

Outlier Privacy

Edward Lui and Rafael Pass

Abstract

We introduce a generalization of differential privacy called \emph{tailored differential privacy}, where an individual's privacy parameter is ``tailored'' for the individual based on the individual's data and the data set. In this paper, we focus on a natural instance of tailored differential privacy, which we call \emph{outlier privacy}: an individual's privacy parameter is determined by how much of an ``\emph{outlier}'' the individual is. We provide a new definition of an outlier and use it to introduce our notion of outlier privacy. Roughly speaking, \emph{$\eps(\cdot)$-outlier privacy} requires that each individual in the data set is guaranteed ``$\eps(k)$-differential privacy protection'', where $k$ is a number quantifying the ``outlierness'' of the individual. We demonstrate how to release accurate histograms that satisfy $\eps(\cdot)$-outlier privacy for various natural choices of $\eps(\cdot)$. Additionally, we show that $\eps(\cdot)$-outlier privacy with our weakest choice of $\eps(\cdot)$---which offers no explicit privacy protection for ``non-outliers''---already implies a ``distributional'' notion of differential privacy w.r.t.~a large and natural class of distributions.