Data Deletion with Provable Security

In many systems one of the most important and essential functionalities necessary for secure data processing is the permanent and irreversible deletion of stored bits. According to recent results, it is possible to retrieve data from numerous (especially magnetic) data storage devices, even if some erasing techniques like wiping have been applied. In fact, in many cases a powerful adversary is able to read information that has been many times overwritten. In our paper we present a new approach to data storage for which a provably secure data deletion seems to be possible. The core idea is based on a particular way of data coding and is generally independent on physical features of the data storage device, so this approach is not limited to magnetic drives. Furthermore, it does not require any special-purpose "secure" device. The usage of a software drivers or installation of modified firmware is sufficient. We provide rigid mathematical analysis of security of the proposed scheme for some scenarios even in the presence of an extremely powerful adversary. Our approach offers all of this for the price of speed and storage overhead. However, even under pessimistic assumptions this scheme remains fairly practical. © 2009 Springer Berlin Heidelberg.