Sampling and Partitioning for Differential Privacy
Authors: Hamid Ebadi, Thibaud Antignac, David Sands
Venue: 14th Annual Conference on Privacy, Security and Trust (PST 2016), pp. 664–673
Abstract
Differential privacy enjoys increasing popularity thanks to both a precise semantics for privacy and effective enforcement mechanisms. Many tools have been proposed to spread its use and ease the task of the concerned data scientist. However, their implementation proves to be delicate, and introduce flaws by falsifying some of the theoretical assumptions made to guarantee differential privacy.
This paper focuses on a key mechanism that tools do not support well: sampling. We demonstrate an attack on PINQ (McSherry, SIGMOD 2009) relying on the difference between its internal mechanics and the formal theory for the sampling operation. We then study a range of sampling and partitioning methods and show how they can be correctly implemented in a system for differential privacy.
Keywords: differential privacy, sampling, partitioning, PINQ
Citation
Ebadi, H., Antignac, T., and Sands, D. (2016). Sampling and partitioning for differential privacy. 2016 14th Annual Conference on Privacy, Security and Trust (PST), pp. 664–673.