Visible to the public Tight on Budget?: Tight Bounds for r-Fold Approximate Differential Privacy

TitleTight on Budget?: Tight Bounds for r-Fold Approximate Differential Privacy
Publication TypeConference Paper
Year of Publication2018
AuthorsMeiser, Sebastian, Mohammadi, Esfandiar
Conference NameProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
ISBN Number978-1-4503-5693-0
Keywordscontinual observation, Differential privacy, pubcrawl, r-fold composition, Resiliency, Scalability, security, Stochastic computing

Many applications, such as anonymous communication systems, privacy-enhancing database queries, or privacy-enhancing machine-learning methods, require robust guarantees under thousands and sometimes millions of observations. The notion of r-fold approximate differential privacy (ADP) offers a well-established framework with a precise characterization of the degree of privacy after r observations of an attacker. However, existing bounds for r-fold ADP are loose and, if used for estimating the required degree of noise for an application, can lead to over-cautious choices for perturbation randomness and thus to suboptimal utility or overly high costs. We present a numerical and widely applicable method for capturing the privacy loss of differentially private mechanisms under composition, which we call privacy buckets. With privacy buckets we compute provable upper and lower bounds for ADP for a given number of observations. We compare our bounds with state-of-the-art bounds for r-fold ADP, including Kairouz, Oh, and Viswanath's composition theorem (KOV), concentrated differential privacy and the moments accountant. While KOV proved optimal bounds for heterogeneous adaptive k-fold composition, we show that for concrete sequences of mechanisms tighter bounds can be derived by taking the mechanisms' structure into account. We compare previous bounds for the Laplace mechanism, the Gauss mechanism, for a timing leakage reduction mechanism, and for the stochastic gradient descent and we significantly improve over their results (except that we match the KOV bound for the Laplace mechanism, for which it seems tight). Our lower bounds almost meet our upper bounds, showing that no significantly tighter bounds are possible.

Citation Keymeiser_tight_2018