How to delete one person from an archive you promised never to change

A bank keeps seven years of transaction records in write-once storage because its regulator requires that nothing can ever be quietly altered. On a Tuesday, a customer exercises their right to erasure. Both obligations are real, both are enforceable, and on the face of it one of them has to lose.

This is the single most common objection we hear from compliance teams, and it is a good objection. It deserves a better answer than the three that are usually offered.

The three answers that don’t work

Don’t use immutable storage.This resolves the conflict by discarding the thing the auditor wanted. If records can be edited, the archive no longer demonstrates anything about what happened seven years ago; it demonstrates what someone was willing to type last week. Most regulated firms cannot take this option, and the ones that can usually shouldn’t.

Restore, delete, recompress, re-seal.Operationally miserable — you are rehydrating terabytes to remove kilobytes — but the real problem is evidentiary. The new archive has a new hash. Every attestation, every signature, every auditor’s note that referenced the old one now points at something that no longer exists. You have to assert that the only difference is one person’s data, and assertion is exactly what the archive was supposed to replace.

Redact in place.Overwrite the personal fields, keep everything else. This mutates a write-once store, which either your storage layer forbids or your tamper-evidence catches, and quite rightly: from the outside, “we redacted one customer” and “we altered a record we didn’t like” are the same operation.

The archive’s value comes from the fact that it cannot be changed. Any erasure that works by changing it has spent the thing it was protecting.

The mechanism that does work

Encrypt each data subject’s personal data under a key that belongs only to them. To erase that person, destroy their key. The ciphertext stays exactly where it is. Nothing is decompressed, nothing is rewritten, and the archive’s bytes are identical before and after.

This is crypto-shredding, and it is not a new idea — it is how key management has handled decommissioning for years. What is worth spelling out is why it is the only approach that survives contact with a tamper-evident archive: it is the one erasure method that is not a mutation. The subject’s data becomes permanently unrecoverable without a single byte of the archive changing.

The consequence is the part that matters to an auditor:

An auditor who recorded the archive’s hash in 2026 can re-verify it in 2031, after forty erasure requests have been processed, and it still matches. The erasures did not weaken the integrity guarantee, because they never touched the bytes the guarantee is computed over. The two obligations stop competing.

What the regulator actually asks

Article 17 requires erasure “without undue delay”, and Article 19 requires you to communicate it. Neither prescribes a mechanism. The operative question a supervisory authority asks is whether the data has been rendered permanently inaccessible, and whether you can evidence that. South Africa’s POPIA reaches the same place through section 24 by a different route.

So the deliverable is not really the deletion. It is four claims, evidenced:

1. This specific subject’s data is permanently unrecoverable.
2. It happened on this date.
3. Nothing else in the archive was affected.
4. Whoever checks this later doesn’t have to take our word for any of it.

The fourth is the one vendors skip. An erasure you can only confirm by asking the vendor whose storage it is has the same evidentiary weight as an email saying “done”. The certificate has to be verifiable independently — by the customer, by an auditor, by a regulator, without our involvement and after we are gone.

Where this gets harder than the marketing suggests

The cryptography is the easy part. Three things are genuinely hard, and anyone selling you this should say so unprompted.

Proving a key is gone is an operational problem, not a mathematical one. You can prove a ciphertext cannot be decrypted withouta key. You cannot prove, by mathematics alone, that no copy of the key exists anywhere. That claim rests on key custody: where keys were generated, what held them, what the destruction procedure was, and what independent record exists of it. Crypto-shredding shifts the burden from “did you delete the data” to “can you account for the key” — which is a much better question to be asked, but it is still a question you must be able to answer.

Copies outside the archive are still copies.If the same personal data sits in a warehouse, a BI extract, three CSVs on a laptop and a vendor’s inbox, erasing it from the archive erases it from the archive. This is a data-mapping problem and no format solves it. Be suspicious of anything sold as end-to-end erasure that never asks where else your data lives.

Signatures have a shelf life; ciphertext has a longer one.The AES-256 used for the payload is comfortable against foreseeable quantum attack — Grover’s algorithm costs it half its bits and 128 is still out of reach. An Ed25519 signature on the erasure certificate is a different story: a sufficiently capable quantum computer breaks it, and a certificate is meant to be checkable in fifteen years. Our answer is a dual-signed certificate — SLH-DSA (FIPS-205) alongside Ed25519 — available on the century tier, while the default path remains Ed25519 only, and dual-signing is opt-in via at1 erase --pq from version 0.1.80. If your retention horizon runs past a decade, make that choice when the certificate is issued — it cannot be applied to one that already exists.

Why we built it this way

We came at this from compression rather than compliance, which turned out to be an advantage. If you are already restructuring data to store it smaller, encrypting per subject and keeping the archive queryable in place is a design decision available to you at the start. Bolting per-subject erasure onto a format that was never designed for it is how you end up with restore-and-recompress.

The result ships as at1 erase inside the Provably-Erasable Archive: erase a subject, get a certificate, and the archive hash before and after are the same value. If that last claim is wrong, it is falsifiable in about a minute, which is roughly the standard any of this should be held to.

• The mechanics, in the buyer’s words: GDPR Article 17 and your backups
• South African context: POPIA retention and erasure
• What a certificate can and cannot prove: the follow-up piece