Algorithms with More Granular Differential Privacy Guarantees

Differential Privacy (DP) [DMNS06] provides a strict worst-case privacy guarantee -- even an adversary that knows the entire dataset except for one bit of information about one individual cannot learn that bit, even when the dataset and the bit in question are arbitrary. Since its inception, researchers have sought to relax the DP definition in order to permit better data analysis while still providing meaningful privacy guarantees [DP19]. The only approach to relaxing the definition of DP that has gained widespread use -- albeit not acceptance -- is quantitative relaxation. That is, it is common to set the main privacy parameter (usually denoted by ε) to be larger than the theory allows us to easily interpret. More precisely, the privacy loss bound ε is used to quantify the tolerable accuracy with which an adversary can learn the unknown bit. Theory would suggest that ε 1 provides a good privacy guarantee, and that the guarantee rapidly degrades if we further increase ε. The setting ε = 10 permits a sensitive bit to be revealed with 99.995% accuracy, if we are unlucky enough to be in a truly worst-case setting.