Lethe: Secure Deletion by Addition

Appeared in Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems (CHEOPS ’23).

Abstract

Modern data privacy regulations such as GDPR, CCPA, and CDPA stipulate that data pertaining to a user must be deleted without undue delay upon the user’s request. Existing systems are not designed to comply with these regulations and can leave traces of deleted data for indeterminate periods of time, often as long as months.

We developed Lethe to address these problems by providing fine-grained secure deletion on any system and any storage medium, provided that Lethe has access to a fixed, small amount of securely-deletable storage. Lethe achieves this using keyed hash forests (KHFs), extensions of keyed hash trees (KHTs), structured to serve as efficient representations of encryption key hierarchies. By using a KHF as a regulator for data access, Lethe provides its secure deletion not by removing the KHF, but by adding a new KHF that only grants access to still-valid data. Access to the previous KHF is lost, and the data it regulated securely deleted, through the secure deletion of the single key that protected the previous KHF.

Publication date:
May 2023

Authors:
Eugene Chou
Leo Conrad-Shah
Austen Barker
Andrew Quinn
Ethan L. Miller
Darrell D. E. Long

Projects:
Secure File and Storage Systems

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{chou-cheops23,
  author       = {Eugene Chou and Leo Conrad-Shah and Austen Barker and Andrew Quinn and Ethan L. Miller and Darrell D. E. Long},
  title        = {Lethe: Secure Deletion by Addition},
  booktitle    = {Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems (CHEOPS ’23)},
  month        = may,
  year         = {2023},
}