Policy-based Secure Deletion

Securely deleting data from storage systems has become difficult today. Most storage space is provided as a virtual resource and traverses many layers between the user and the actual physical storage medium. Operations to properly erase data and wipe out all its traces are typically not foreseen. This paper introduces a cryptographic model for policy-based secure deletion of data in storage systems, whose security relies on the proper erasure of cryptographic keys. Deletion operations are expressed in terms of a deletion policy that describes data destruction through deletion attributes and protection classes. A protection class is first applied to the stored data. Later, a secure deletion operation takes attributes as parameters and triggers the destruction of all data whose protection class is deleted according to the policy. No stored data is ever re-encrypted. A cryptographic construction is presented for deletion policies given by directed acyclic graphs; it is built in a modular way from exploiting that secure deletion schemes may be composed with each other. Finally, the paper describes a prototype implementation of a Linux filesystem with policy-based secure deletion.