Connecting Randomized Response, Post-Randomization, Differential Privacy and t-Closeness via Deniability and Permutation
This work provides theoretical insights for researchers in privacy-preserving data analysis, but it is incremental as it builds on known connections without introducing new methods.
The paper explores connections between privacy models like randomized response, differential privacy, and t-closeness through principles of deniability and permutation, showing that these models are more interrelated than commonly thought and that permutation can explain their guarantees.
We explore some novel connections between the main privacy models in use and we recall a few known ones. We show these models to be more related than commonly understood, around two main principles: deniability and permutation. In particular, randomized response turns out to be very modern in spite of it having been introduced over 50 years ago: it is a local anonymization method and it allows understanding the protection offered by $ε$-differential privacy when $ε$ is increased to improve utility. A similar understanding on the effect of large $ε$ in terms of deniability is obtained from the connection between $ε$-differential privacy and t-closeness. Finally, the post-randomization method (PRAM) is shown to be viewable as permutation and to be connected with randomized response and differential privacy. Since the latter is also connected with t-closeness, it follows that the permutation principle can explain the guarantees offered by all those models. Thus, calibrating permutation is very relevant in anonymization, and we conclude by sketching two ways of doing it.