Technical Perspective on 'History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures'

Background. Retention regulations mandate that once sensitive data is deleted, no evidence about its past existence should be recoverable, even by a determined adversary. Typically, data is physically deleted from the storage medium by using compliant erasure mechanisms. Nevertheless, evidence of past deletes and of the existence of the deleted data itself cannot be eliminated by simply overwriting the data. This is because modern data processing comes with significant side-effects pervading all the layers of a computing system. To fully expire data and implement compliant erasure, transactions that have previously involved the data, across all key layers of the computing system, need to be identified and possibly rolled back.