UC Santa Cruz

Modern general data privacy regulations in Europe (GDPR) stipulate that, at a user’s request, data pertaining to them is deleted without undue delay. Existing storage systems are not equipped to provide secure deletion, leaving traces of deleted data for indeterminate periods of time, sometimes on the order of months. Current approaches to secure deletion, overwrite erasure and cryptographic erasure, are also unsatisfactory. Overwrite erasure requires numerous in- place overwrites that are difficult on flash media and negatively impact media lifetime. With cryptographic erasure, secure deletion of data is tied to secure deletion of the encryption key. This quickly becomes a key management problem since enabling fine-grained deletion requires that a key must be maintained for each data block that may be deleted. To address these prob- lems, we propose Lethe, a new system that provides fine-grained secure deletion regardless of storage medium by utilizing keyed hash trees. With keyed hash trees, Lethe is able to drastically reduce the amount of key material that must be stored and forgotten while still providing the necessary amount of keys required for fine-grained secure deletion. The amount of key material that needs to be securely deleted in Lethe does not increase linearly with the amount of data that is to be securely deleted. With Lethe, the fine-grained secure deletion of any amount of data requires only a single key to be securely forgotten.