Sensitivity computation for user-defi ned functions in Differential Privacy systems

Abstract

Differential privacy (DP) is emerging as a viable solution to release statistical information about a population without compromising data subjects’ privacy. A standard way to achieve DP is by adding calibrated noise to the result of some statistical analysis. To account for the impact an individual’s data have on the result of an analysis, the noise needs to be calibrated to the maximal change in the observable result of the analysis that occurs as an individual’s data changes. This is formalized through the notion of sensitivity.

In this work, we construct a small DSL for writing queries on datasets. The DSL is capable of automatically computing the global sensitivity of said queries. Using this DSL, we improve an existing implementation of the MWEM algorithm by stepping away from manual tuning of the sensitivity parameter for every set of queries instead of adjusting it automatically.

The underlying mechanism for computing the sensitivity is a technique for analyzing the range of user-defined functions, implemented as a data generic library in Haskell. The technique works on enumeration types and may be used `a la carte in scenarios where range analysis of user-defined functions is desirable.