Smooth sensitivity and sampling in private data analysis

TLDR

The noise magnitude in private data analysis depends on both the function and the database, and ensuring it does not leak information is a key challenge; this work provides the first formal analysis of instance‑based noise in this context. The authors propose a generic framework for private data analysis that releases aggregate functions with instance‑based additive noise. The framework calibrates noise magnitude to the smooth sensitivity of the function on the database, adding instance‑based additive noise. The framework expands the applicability of output perturbation, enabling privacy‑preserving release of statistics with small random noise.

Abstract

We introduce a new, generic framework for private data analysis.The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.Our framework allows one to release functions f of the data withinstance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x. The new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy.