The right to be forgotten, also known as the right to erasure, is the right of individuals to have their data erased from an entity storing it. The status of this long held notion was legally solidified recently by the General Data Protection Regulation (GDPR) in the European Union. As a consequence, there is a need for mechanisms whereby users can verify if service providers comply with their deletion requests. In this work, we take the first step in proposing a formal framework, called Athena, to study the design of such verification mechanisms for data deletion requests – also known as machine unlearning – in the context of systems that provide machine learning as a service (MLaaS). Athena allows the rigorous quantification of any verification mechanism based on hypothesis testing. Furthermore, we propose a novel verification mechanism that leverages backdoors and demonstrate its effectiveness in certifying data deletion with high confidence, thus providing a basis for quantitatively inferring machine unlearning. We evaluate our approach over a range of network architectures such as multi-layer perceptrons (MLP), convolutional neural networks (CNN), residual networks (ResNet), and long short-term memory (LSTM) and over 6 different datasets. We demonstrate that: (1) our approach has minimal effect on the accuracy of the ML service but provides high confidence verification of unlearning, even if multiple users employ our system to ascertain compliance with data deletion requests, and (2) our mechanism is robust against servers deploying state-of-the-art backdoor defense methods. Overall, our approach provides a foundation for a quantitative analysis of verifying machine unlearning, which can provide support for legal and regulatory frameworks pertaining to users’ data deletion requests.

Abstract Quantifying the privacy loss of a privacy-preserving mechanism on potentially sensitive data is a complex and well-researched topic; the de-facto standard for privacy measures are ε-differential privacy (DP) and its versatile relaxation (ε, δ)-approximate differential privacy (ADP). Recently, novel variants of (A)DP focused on giving tighter privacy bounds under continual observation. In this paper we unify many previous works via the privacy loss distribution (PLD) of a mechanism. We show that for non-adaptive mechanisms, the privacy loss under sequential composition undergoes a convolution and will converge to a Gauss distribution (the central limit theorem for DP). We derive several relevant insights: we can now characterize mechanisms by their privacy loss class, i.e., by the Gauss distribution to which their PLD converges, which allows us to give novel ADP bounds for mechanisms based on their privacy loss class; we derive exact analytical guarantees for the approximate randomized response mechanism and an exact analytical and closed formula for the Gauss mechanism, that, given ε, calculates δ, s.t., the mechanism is (ε, δ)-ADP (not an over-approximating bound).

Computing differential privacy guarantees is an important task for a wide variety of applications. The tighter the guarantees are, the more difficult it seems to be to compute them: naive bounds are simple additions, whereas modern composition theorems require either a search over a potentially confusing parameter space (for the composition theorem of Kairouz, Oh, and Visvanath), require computing many moments (for Rényi DP) or finding parameters of a function that limits the privacy loss (for concentrated DP). The best known approach for tight differential privacy bounds, called Privacy Buckets, provides requires running a fairly complex implementation of numerical approximations. In this work, we provide an easy-to-use interface for computing state-of-the-art differential privacy guarantees by simply accessing a website. Guarantees for the widely used Laplace mechanism and for the similarly popular Gauss mechanism can be computed by simply stating the scale parameter of the noise, the sensitivity, and the number of compositions. Privacy guarantees for more complex distributions can be computed by uploading two histograms. This work bridges the gap between the best known theoretical results for computing differential privacy guarantees and privacy analysts and users benefiting from such guarantees.

Many privacy-enhancing technologies, in particular anonymous communication networks (ACNs) as a key building block, suffer from a lack of a sufficient number of participants. Without high user participation, ACNs are vulnerable to traffic analysis attacks. The only ACN with a high number of participants (around 1.5 million users) is Tor. Yet, Tor is prone to traffic analysis attacks traffic pattern attacks. While other ACNs have been proposed that are even secure against global attackers, they are not scalable and suffer from a low number of participants, since even a perfect ACN can at most hide a user among all participating users. These ACNs are in a vicious circle: the lack of participants leads to low degree of anonymity, and a low degree of anonymity makes these ACNs unattractive for users. In this work, we break this vicious cycle by studying the question: Can an anonymous communication network be strengthened by "forced" participation? What privacy guarantees and performance can such an ACN provide? We develop CoverUp, a system that "forces" visitors of highly accessed websites (entry servers) to become involuntary participants of an ACN. CoverUp triggers users to participate in a centralized, constant-rate mix by leveraging basic functionality of their browsers to execute (JavaScript) code served by the entry servers. Candidates for entry servers could be universities or news sites. They would let a distinct CoverUp server provide (via an iframe) JavaScript code to the end-users' browsers, which in turn makes them participate in the ACN via a mix server. Visitors of these entry servers' websites become (involuntary) participants of an ACN, creating cover traffic for voluntary participants. For voluntary participants, we developed a browser extension that renders their CoverUp requests indistinguishable from the cover traffic of involuntary participants.