Existing software-based data erasure programs can be summarized as following the same one-bit-returnprotocol: the deletion program performs data erasure and returns either success or failure. However, such a onebit-return protocol turns the data deletion system into a black box – the user has to trust the outcome but cannoteasily verify it. This is especially problematic when the deletion program is encapsulated within a Trusted PlatformModule (TPM), and the user has no access to the code inside.In this paper, we present a cryptographic solution that aims to make the data deletion process more transparentand verifiable. In contrast to the conventional black/white assumptions about TPM (i.e., either completely trust ordistrust), we introduce a third assumption that sits in between: namely, “trust-but-verify”. Our solution enables a userto verify the correct implementation of two important operations inside a TPM without accessing its source code: i.e.,the correct encryption of data and the faithful deletion of the key. Finally, we present a proof-of-concept implementationof the SSE system on a resource-constrained Java card to demonstrate its practical feasibility. To our knowledge, thisis the first systematic solution to the secure data deletion problem based on a “trust-but-verify” paradigm, togetherwith a concrete prototype implementation.