It isn’t that hard to combine soft deletes with delayed hard deletes: generate a new encryption key every day for “data deleted today”, and encrypt deleted data with it. After X days, destroy the decryption key.
If you use asymmetric encryption, you can keep the group of people who who can recover “deleted data” small. You could even have an independent party generate your encryption key pair, give you the encryption key, and your customer, on request, the decryption key (I think there is a business model for a non-profit here).
Because the key is smaller, it is easier to make sure you deleted every copy of that key than that you deleted every copy of the data. The data also might be part of a larger backup that you would have to take apart and reassemble in order to delete the data, or might be in a place where doing that is costly (e.g. on Amazon Glacier)
> generate a new encryption key every day for “data deleted today”,
The question is not can we encrypt at storage. We’re now talking about encrypting as a soft-deletion method, which means we need to know everywhere the data is stored at deletion time, whether to delete it or to encrypt it with this new “deletion” key.
Thanks for raising that issue, I was somewhat confused by the mentioning of encryption as a soft-deletion method... it made precious little sense to me, but everybody seemed to go along with it and I thought I was missing something very fundamentally ’right’ about that idea. Turns out it’s not so.
If you use asymmetric encryption, you can keep the group of people who who can recover “deleted data” small. You could even have an independent party generate your encryption key pair, give you the encryption key, and your customer, on request, the decryption key (I think there is a business model for a non-profit here).