Esfandiar Mohammadi, ETH Zurich
From 12.00 until 13.30
At CNB/F/110 (Lunch) + CNB/F/100.9 (Seminar), ETH Zurich
Universitätstrasse 6, 8092 Zurich
Abstract:
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 well-established 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. In other scenarios, such as for the Gaussian mechanism or for real-world timing leakage data, we show, however, that our method provides significantly tighter bounds. We illustrate 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.
This project is a joint work with Sebastian Meiser (UCL). For more information on the project and an implementation, please have a look at http://e.mohammadi.eu/ratio-buckets.html .