The rising collection of data from our personal lives in sectors as varied as health care, advertising, and criminal justice has inspired a surge of new privacy legislation and protections for data subjects worldwide. Since taking effect in May 2018, the General Data Protection Regulation (GDPR) has provided Europeans greater rights over the processing of their personal data, including rights to erase, access, correct, and object. In this work we focus on a right to erasure or the right to be forgotten.

These laws raise two important questions: What does it mean for a data controller to delete a person's data? and How can a data controller determine whether they are compliant with erasure? Given that these laws concern computing systems, we argue that a mathematically rigorous definition of deletion is necessary for providing meaningful guarantees within such systems.

We provide a framework that mathematically unifies previous partial answers to the above questions. The power of this definition comes from its general applicability. It allows us to analyze data controllers that intuitively satisfy a right to erasure, but did not fit into prior models; furthermore, it enables us to compare the erasure compliance of vastly different data controllers and different implementations of the same functionalities. In particular, the definition clarifies the relationships between other constraints such as differential privacy, pan-privacy, and history independence.