In an upcoming paper (to be published by IEEE Transactions on Dependable and Secure Computing, 2015), we (with Dylan Clarke and Avelino Zorzo) investigate the secure data deletion problem. This problem concerns the guaranteed deletion of digital data using software means, which has been an active topic in recent years with quite a number of publications on major security conferences (Oakland, CCS, USENIX Security etc).

We observe that in all published solutions, the underlying data deletion system is (implicitly) assumed to be a trusted black-box. When the user instructs the system to delete data, she receives one bit in return: success or failure. The user has to trust the outcome, but cannot easily verify it. Demanding the deletion program to be open-source appears to be a solution, but it does not address the real problem since the actual code used in the run-time is opaque to the user. This is especially problematic when the software program is encapsulated within a tamper resistant hardware, and it’s impossible for users to access the internal code.

For those who work on electronic voting, the above problems should sound familiar. A black-box voting system works in exactly the same way. Take the standard Direct Electronic Voting (DRE) machine as an example. The DRE system records voters’ choices through a touch screen interface. At the end of the election day, the system announces the final tally, which voters have to trust but cannot easily verify. The source code is usually not publicly available as it may contain IPR. Even it were available, there is no guarantee that the software actually running in the DRE system is the same as the source code released in the public domain.

It’s exactly the above problems that promoted the thirty-year research on “verifiable e-voting”. Today, the importance of enabling public verifiability for an e-voting system has been widely accepted. Established solutions generally involve using cryptography to allow a voter to “trust-but-verify” a voting system rather than “completely-trust” it. The essence of those solutions is succinctly summarized by Ron Rivest as ”software independence”: namely, one should be able to verify the integrity of software by verifying the output of the software rather than its source code.

While the trust-but-verify principle has been universally adopted in the e-voting community, it has so far been almost entirely neglected in the field of secure data deletion. In this new paper, we initiated an investigation of applying the “trust-but-verify” principle to the data secure problem with a concrete solution, called Secure Storage and Erasure (SSE). The SSE protocol allows public verifiability on two important operations, namely encryption and deletion. More technical descriptions about the solution can be found in the paper (available in IACR ePrint).

It’s worth mentioning that we have implemented a fully functional prototype of the SSE on a resource-constrained Java Card. The source code is publicly available here. This implementation proved to be a non-trivial challenge as there was no precedent to follow. We were severely constrained by the (very limited) set of the APIs available to a Java card, and sometimes had to implement some primitive functions (such as modular multiplication) from scratch in pure software (without any support from the hardware co-processor). Kudos to Avelino Zorzo, who did the bulk of the implementation work during his sabbatical with us at the School of Computing Science in 2013, and also Dylan Clarke, who continued and completed the development work after Avelino left.