A Partitioned Recoding Scheme for Privacy Preserving Data Publishing.

There is growing interest in Differential Privacy as a disclosure limitation mechanism for statistical data. The increased attention has brought to light a number of subtleties in the definition and mechanisms. We explore an interesting dichotomy in parallel composition, where a subtle difference in the definition of a “neighboring database” leads to significantly different results. We show that by “pre-partitioning” the data randomly into disjoint subsets, then applying well-known anony-mization schemes to those pieces, we can eliminate this dichotomy. This provides potential operational benefits, with some interesting implications that give further insight into existing privacy schemes. We explore the theoretical limits of the privacy impacts of pre-partitioning, in the process illuminating some subtle distinctions in privacy definitions. We also discuss the resulting utility, including empirical evaluation of the impact on released privatized statistics.