SoK: Differential privacies

Authors: Damien Desfontaines (ETH Zürich / Google), Balázs Pejó (CrySyS Lab, Dept. of Networked Systems and Services, Budapest University of Technology and Economics)

Volume: 2020
Issue: 2
Pages: 288–313
DOI: https://doi.org/10.2478/popets-2020-0028

Download PDF

Abstract: Shortly after it was first introduced in 2006, differential privacy became the flagship data privacy definition. Since then, numerous variants and extensions were proposed to adapt it to different scenarios and attacker models. In this work, we propose a systematic taxonomy of these variants and extensions. We list all data privacy definitions based on differential privacy, and partition them into seven categories, depending on which aspect of the original definition is modified. These categories act like dimensions: variants from the same category cannot be combined, but variants from different categories can be combined to form new definitions. We also establish a partial ordering of relative strength between these notions by summarizing existing results. Furthermore, we list which of these definitions satisfy some desirable properties, like composition, postprocessing, and convexity by either providing a novel proof or collecting existing ones.

Keywords: Differential privacy, Data privacy, Survey, Systematization of knowledge

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs license.