Crypto-Shredding

Deletion requirements and backup requirements are in direct conflict. Regulation requires that personal data be erasable on request; sound engineering requires immutable backups retained for months and often written to media that cannot be selectively rewritten. Rewriting every historical backup to remove one user's rows is impractical and frequently impossible.

Crypto-shredding resolves it by changing what "erasure" means. Each subject's data is encrypted with a key unique to that subject. Deleting the key renders every copy — primary, replicas, snapshots, archives, offline media — permanently undecipherable. The ciphertext remains and is meaningless.

Why it matters

It is the only widely accepted technique that satisfies both constraints simultaneously, which is why it appears in essentially every mature answer to "how do you delete a user from your backups". Without it, organisations tend to make one of two claims to regulators, both untrue: that backups do not contain the data, or that deletion has been completed when only the primary store was touched.

Implementation patterns

• Per-subject data encryption keys, wrapped by a key-encryption key in a managed key store. Deleting the wrapped key destroys access without touching the data.
• Key deletion as the auditable event. The deletion record proves erasure; the key store's audit log is the evidence. This is far more defensible than attempting to prove absence across many stores.
• Encrypt at the right granularity. Per-user is the usual boundary; per-tenant works for B2B products; per-record is possible and expensive in key-management overhead.
• Handle shared and derived data explicitly. Deduplicated blocks referenced by several users cannot be shredded on one user's request — those need reference counting instead. Derived artefacts (thumbnails, extracted text, embeddings) must be encrypted under the same key, or they survive the shredding.
• Key rotation must preserve shreddability. A rotation scheme that re-encrypts under a shared key silently destroys the property.

Industry example

A consumer file-storage platform faces every version of this problem at once: replicas across regions, snapshots retained for disaster recovery, CDN copies, search indexes over document contents, extracted previews, and — the hardest part — deduplicated blocks shared between users who uploaded the same file.

The design that works separates the two mechanisms cleanly. Reference counting handles shared content: a deletion removes the user's reference, and blocks are collected only at zero references, so another user's identical file is untouched. Crypto-shredding handles the user-specific layer: metadata, keys to their private content, and anything encrypted under their key across backups and archives.

Underneath both sits a deletion orchestrator with a durable manifest, because deletion is a distributed workflow: mark inaccessible immediately, then fan out to every store with retries, tracking completion per target, and able to answer "which store is still outstanding?"

Failure scenarios

• Key backups outliving the data. If the key store's own backups retain deleted keys, nothing was shredded. Key deletion must propagate through key backups, which is a genuinely difficult sub-problem.
• Derived data encrypted under a different key, so previews and extracted text survive.
• Shared keys across users, making per-user shredding impossible after the fact.
• Shredding claimed but access paths remaining — a cached decrypted copy, a plaintext export, a log line containing the content.
• No verification. Deletion is a compliance assertion; sampling deleted identifiers across every store is what turns it from a claim into evidence.

Trade-offs

You gain a defensible, auditable erasure story that works against immutable media, and you pay with key management as a critical-path dependency: lose a key by accident and the data is gone with no recovery, which makes the key store the single most sensitive component in the system. There is also encryption overhead, complexity in analytics over encrypted data, and a hard constraint that any new store must participate in the scheme from day one.

Interview question

"A user requests deletion. Your primary database, three replicas, six months of immutable backups, a search index, a CDN and a deduplicated block store all hold their data. Walk me through what happens, what you tell the user about timing, and how you would prove it later."