Crypto-Shredding

Immutable architectures — event logs, append-only ledgers, versioned object storage, replicated backups — are built on the guarantee that written data is never modified. Erasure requirements demand exactly the modification the design forbids, and the collision is genuine rather than merely awkward.

Crypto-shredding resolves it by making readability, rather than existence, the thing that is deleted. Each subject's personal data is encrypted under a per-subject key held in a key management system. Erasure destroys the key. The ciphertext remains in every log, backup and replica, and is no longer personal data in any usable sense.

Why it matters

The alternatives are all bad. Rewriting history destroys the auditability and reproducibility that the immutable design existed for, and is often impossible across backups, replicas and downstream consumers. Excluding personal data from the log means the log no longer describes what happened. Not honouring erasure is not an option where the requirement is legal.

Crypto-shredding also scales to places rewriting cannot reach: offline backups, archived object storage, data already shipped to a warehouse, and replicas in other regions. One key destruction propagates to every copy simultaneously, because none of them can decrypt.

Implementation patterns

• One key per data subject, not per table or per service — the granularity of the key is the granularity of erasure.
• Envelope encryption: the per-subject key is itself encrypted under a master key, so the subject keys can be stored densely and rotated.
• A strict discipline about what is encrypted. Anything identifying must be inside the envelope; anything outside it survives erasure. Getting this boundary wrong is the principal failure, and it is a data classification exercise before it is a cryptography one.
• Keep structural and non-identifying data in clear text — timestamps, amounts, event types — so aggregate analytics and reconciliation continue to work after erasure. This is the design's main practical benefit: the shape of history survives.
• Key destruction as an auditable, irreversible operation, with its own record — and with the KMS's own backups accounted for, or the key is not actually gone.
• Verify erasure by attempting decryption as a test, rather than trusting that the key deletion happened.
• Handle the shared-data case explicitly: a transaction between two subjects touches two subjects' data, and the model must define whose key protects what.

Industry example

The pattern is standard in event-sourced financial systems, where the ledger must remain immutable for regulatory reconstruction while data-protection law grants erasure rights. Nubank's use of an immutable fact-based data model is a well-known instance of the underlying architecture — regulatory reconstruction requires that facts never be rewritten, so erasure must be implemented by some means other than deletion.

The same technique appears wherever object-storage-backed lakes hold personal data: rewriting Parquet files across a multi-petabyte lake to remove one subject is impractical, and key destruction is the only mechanism that reaches every copy.

Failure scenarios

• Identifying data left outside the envelope — a name in a log line, an email in an index, a subject identifier used as a partition key. The partition-key case is the most common and the most awkward.
• Keys backed up by the KMS's own retention policy, so destruction is reversible and the erasure is not real.
• A key shared across subjects, making individual erasure impossible.
• Downstream systems that decrypted and re-persisted in clear text, which is invisible from the primary system and is where most real failures live.
• Derived data and models trained on decrypted values, which the key destruction does not touch.
• Search indexes built over plaintext, retaining what the store has erased.
• A regulator that does not accept cryptographic erasure as deletion — the legal position is not uniform, and this must be confirmed rather than assumed.

Trade-offs

Crypto-shredding buys erasure without mutation, and costs encryption on every write and decryption on every read of personal fields, a key management system on the critical path, and the permanent loss of the ability to read that data for any purpose — including a legitimate investigation begun after the erasure.

It also shifts the problem to key management, which is now a correctness-critical, availability-critical dependency: losing a key by accident is an unrecoverable data loss event, and a KMS outage becomes a read outage.

The trade is a permanent operational and cryptographic burden in exchange for reconciling immutability with erasure — a burden worth carrying when the architecture is genuinely immutable and the erasure obligation is genuinely legal, and pure overhead in a mutable system where a DELETE would have sufficed.

Interview question

"Our ledger is append-only for regulatory reasons and we have just received an erasure request. Walk me through your approach, then tell me the three places in our estate where the personal data has probably escaped the envelope and what you would do about the one in the partition key."