International Association
for Cryptologic Research

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.