Why 'Provable Data Erasure' Is Really Hard
Or why most people probably shouldn't ask me questions if they want anything other than the brutal truth.
A few days ago, a very nice, earnest developer sent me a message. He was building a tool designed to ensure ‘provable data erasure’, but had the good (or perhaps, bad) enough sense to ask me for a sanity-check first.
It was an interesting problem, and he was quite flattering in his email, so I decided to engage. Originally, I dashed off a few thoughts, but I quickly realized that ensuring provable erasure, like so many things in data protection, is fractally complex:
I’m not here to lambast the developer. The reason I’m posting here today is because I think there’s a lot of knowledge that I’ve amassed being a bitter old data protection crone that might be worth sharing with others.
Tl;Dr: Most organizations can’t prove that data is for reals gone, and truly unrecoverable, for a few different, intractable, and overlapping reasons.
Finding data is hard. Unless you’re starting greenfield (most orgs that actually make money are not), setting up good data quality/management practices early before bad data practices ossify is hard. That usually makes finding data hard.
Even if you’ve gone and hired a good consultancy to help you, most modern companies no longer have a central source of truth. Say you’re a medium-sized software company. You’ve got an HR department, legal, engineering, product development, IT, finance, biz dev, etc. Within each of those organizations sit various data repositories, applications, SaaS tools, people’s individual file stores, shadow IT, etc. And then there’s all the centrally-managed stuff (email, SharePoint, CRM, etc.)Data can be copied. Once a file can be copied, even if it’s encrypted, proving deletion or un-recoverability for all copies is hard, if not actually impossible, especially if you don’t have #1 nailed down. Unless you have a new process for handling information that does not involve classical file architecture, e.g., you’re doing some sort of quantum-encryption-state magic or weird blockchain/sharding thing where there’s no ‘file’ ever created in the first place, you’re going to have a time getting around the fact that 100 versions of HR_Org_Chart-2026-05-01(1)review (1)(2).docx are floating around in people’s OneDrives, Google Docs, Slack threads, stored locally in C:/Users/Bob/Documents, etc.
Even if you do something like key-based encryption for all files, you still need to prove that you have at least destroyed every copy of the key.If you are doing fancy magic. Good luck getting everyone to migrate away from what they already know & use to some completely new architecture. Have you met lawyers or accountants ever? And good luck getting all the SaaS and application providers to shift from their proprietary / standard file formats (some of which have been functioning for 50+ years!) to your new hotness. Gonna take time and a lot of buy-in.
“Deletion” in general is tricky. Or rather, enforced hard (versus soft) deletion is trickier than most realize. Some data, either legally or practically can’t be deleted. Try as I might, I will never get the IRS to delete my tax data. Other data exists in read-only / immutable file systems, and the only ‘deletion’ you’ve got is to nuke the entire database (or retrain the model, but I’ll get to that below).
Some systems also have the added problem of making deletion really hard. I had a client once who was using a legacy database that no one in the organization knew how to maintain. You could add files to it forever, but no one knew how to delete anything from it. I mean, I’m sure it was possible to delete files, but the guys who coded the thing had long since retired/died and left no notes, so functionally for them, it was impossible.Non-technical people. Within each of those organizations sit people who are primarily not technical, and couldn’t tell you what a database was, or where the audit logs were, who they were sharing files with, what retention policies apply, if retention policies were enforced, or even what to look for.
While some systems may be connected and thus manageable by IT (e.g., OAuth, integrations, SDKs, MCPs), loads aren’t. They’re siloed, specialized, unknown to the technical / compliance side, and locked down for folks with a need to know, but not necessarily the technical discovery skills to answer an erasure question.Technical people also don’t know. But even technical people frequently don’t know what files exist in the organization because the organization is huge, has no coherent data structure, and do not hire the fancy data consultancies or people that can create and maintain such a system. No one is getting paid to think about whether a file is for-reals deleted or not. Most organizations don’t even know what data provenance or attestation is. Compliance is a cost-center, and data subject rights are an enormous cost to organizations that treat it like a chore.
Reviewing audit logs sucks and does not scale. Audit trails and logs are great, but require manual or very robust automated review and it’s still easy to miss stuff. Even with AI / LLMs that can eliminate the toil of audit review, there’s no way to guarantee provable erasure has occurred across all systems because the points I mentioned above. Also, people are busy, sloppy, disinterested, distracted, confused, or any number of other very human conditions that make sanity checking and validation hard.
Trust Issues. Most data protection laws require downstream notification to sub-processors, necessitating that they delete data. That’s a fun theory, but almost impossible to enforce. Say, Alice’s company outsources a file to Bob and later requires deletion; getting a guarantee that Bob actually deleted it is impossible because copies and there is no way for Alice to audit Bob. Now substitute Bob for Google, Oracle, Microsoft, Hubspot, etc. There is no practical, realistic way that Alice’s company will ever be able to demonstrably prove that Microsoft or Google has effectuated Article 19 erasure requests across all systems, even if everybody agreed contractually that they would.
See, the thing is, a contract is a pinky-promise that’s wrapped in paperwork and a small threat of enforceability by a court. It only means something if you can get a court to agree and force action. It’s not scalable, practical, or even contractually permissible for Alice to run to Microsoft/Google and check every time she requests a file be deleted, and there’s nothing forcing the companies to be honest because she won’t have the means to sue. At best, she might be able to get a once-a-year audit, at her own expense, and I guess she could batch check all the downstream erasure requests, but ...AI and training data. Hooboy, do I have some thoughts on this. Algorithmic disgorgement is possible, but Europe tends to be scared to apply it, and ain’t no way is this happening under the current FTC. But it is possible at least, I guess.
The cost is high, but the risks are low. Most firms act rationally, and recognize that
a) data subject rights are not profit-maximizing;
b) data subjects have no meaningful way to check;
c) regulators are resource-constrained and also have no way to police, monitor, or enforce for perfect compliance;
d) Unless the organization is already doing a load of OTHER hinky shit with data, the likelihood they will ever need to ‘prove to a regulator’ that they actually deleted data is microscopically low.
In the grand scheme of things, unless you have the time and ability to do a full audit or sue, it’s a bit of a Schrödinger's cat problem. Nobody is incentivized to check if the cat is alive or dead, and it exists in a super-positional state of being probably dead for compliance purposes, even if it might be still floating around i Bob’s local file store. That’s usually good enough.
Also, if you’re at the point where you’ve done lots of bad things with data (e.g., Meta), full compliance with data subject erasure rights is not going to be high on the list of what they get fined for.
FWIW, I’d hazard that most regulators themselves don’t have a perfectly guaranteed process either. Hell, I’d be suspect if they even have consistently applied retention policies across all systems.Unknown unknowns. All of this + a dozen other things I haven’t articulated.
I’m sure I’m missing a few things, and who knows, I could be wrong! I would love to be wrong on this, because I think it’s a legitimately bad problem that deserves a solution. Not quite like say, curing cancer, fixing the overheating planet, or preventing the gradual disempowerment of humanity due to concentrated tech power, but you know, it’s up there.
And if you are also a glutton for punishment, or want to provide me with interesting blog fodder, particularly around tech extensity, privacy, gradual disempowerment, and power dynamics, please drop me a message, leave a comment, or check out my fancy new consultancy page.