Ratio Buckets: A Numeric Method for k-fold Tight Differential Privacy

Privacy guarantees of a privacy-enhancing system have to be robust against thousands of observations for many realistic application scenarios, such as anonymous communication systems, privacy-enhancing database queries, or privacy-enhancing machine-learning methods. The notion of r-fold Approximate Differential Privacy (ADP) offers a framework with clear privacy bounds and with composition theorems that capture how the ADP bounds evolve after r observations of an attacker. Previous work, however, provides privacy bounds that are loose, which results in an unnecessarily high degree of recommended noise, leading to low accuracy. This work improves on previous work by providing upper and lower bounds for r-fold ADP, which enables us to quantify how tight our bounds are. We present a novel representation of pairs of distributions, which we call ratio buckets. We also devise a numerical method and an implementation for computing provable upper and lower bounds with these ratio buckets for ADP for a given number of observations. In contrast to previous work, our bucket method uses the shape of the probability distributions, which enables us to compute tighter bounds. Our studies indicate that previous work by Kairouz et al. provides tight bounds for the Laplace mechanism. However, we show that our work provides significantly tighter bounds for other scenarios, such as the Gaussian mechanism or for real-world timing leakage data. We show that it is beneficial to conduct a tight privacy analysis by improving, as a case study, the privacy analysis of the anonymous communication system Vuvuzela. We show that for the same privacy target as in the original Vuvuzela paper, 10 times less noise already suffices, which significantly reduces Vuvuzela's overall bandwidth requirement