On Sampling, Anonymization, and Differential Privacy: Or, k-Anonymization Meets Differential Privacy

Understand

This paper aims at answering the following two questions in privacy-preserving data analysis and publishing: What formal privacy guarantee (if any) does $k$-anonymization provide? How to benefit from the adversary's uncertainty about the data? We have found that random sampling provides a connection that helps answer these two questions, as sampling can create uncertainty.

• The main result of the paper is that $k$-anonymization, when done "safely", and when preceded with a random sampling step, satisfies $(\epsilon,\delta)$-differential privacy with reasonable parameters.
• This result illustrates that "hiding in a crowd of $k$" indeed offers some privacy guarantees.
• This result also suggests an alternative approach to output perturbation for satisfying differential privacy: namely, adding a random sampling step in the beginning and pruning results that are too sensitive to change of a single tuple.