  Garg, Goldwasser and Vasudevan (Eurocrypt 2020) invented the notion of
deletion-compliance to formally model the "right to be forgotten", a concept
that confers individuals more control over their digital data. A requirement of
deletion-compliance is strong privacy for the deletion requesters since no
outside observer must be able to tell if deleted data was ever present in the
first place. Naturally, many real world systems where information can flow
across users are automatically ruled out.
  The main thesis of this paper is that deletion-compliance is a standalone
notion, distinct from privacy. We present an alternative definition that
meaningfully captures deletion-compliance without any privacy implications.
This allows broader class of data collectors to demonstrate compliance to
deletion requests and to be paired with various notions of privacy. Our new
definition has several appealing properties:
  - It is implied by the stronger definition of Garg et al. under natural
conditions, and is equivalent when we add a privacy requirement.
  - It is naturally composable with minimal assumptions.
  - Its requirements are met by data structure implementations that do not
reveal the order of operations, a concept known as history-independence.
  Along the way, we discuss the many challenges that remain in providing a
universal definition of compliance to the "right to be forgotten."
