What a deletion certificate actually proves

A customer asks you to delete their data. You do. Six months later their lawyer asks you to prove it. What, exactly, do you hand over — and what does the thing you hand over actually establish?

In most organisations the answer is a PDF with a logo, a date and a sentence saying the data was deleted. That is not evidence. It is the same claim as the email you already sent, rendered in a nicer font. If the dispute is about whether you did what you said, a document you produced saying you did it does not move anyone.

What a real certificate binds

A certificate becomes evidence when it cryptographically commits to enough specifics that it cannot be quietly reused, backdated or edited. At minimum:

subject_id             : the data subject's identifier
archive_hash_before    : the archive's content hash before
archive_hash_after     : and after (equal, by construction)
record_groups_erased   : how many record groups were destroyed
key_destruction_proof  : a commitment to the destroyed key
payload_hash           : hash of the caller's own record of the request
erased_at              : timestamp
issuer                 : a free-text label of who claims to have done this
signature              : over all of the above

Note what that list does not contain, because we described it wrongly here for a week and the correction is below. The subject identifier is written in clear text, not hashed. There is no field naming which archive instance the certificate refers to — only a content hash, which every replica and backup of that archive shares. And issuer is free text bound to no key, so it states whoclaims to have performed the erasure, not who did.

Each of those is a real limit on what the certificate proves, and each is fixable. We are fixing them. Until then this is what the artefact actually contains.

What it proves

1. At the stated time, the named issuer asserted that this subject’s key was destroyed in this archive.
2. The certificate has not been altered since it was signed.
3. The archive it refers to is identifiable, and its integrity is independently checkable.
4. Anyone holding it can verify all of the above without contacting the issuer.

That fourth point does more work than it appears to. A certificate that can only be validated by logging into the vendor’s console is worth nothing once the vendor is replaced, acquired or wound up — and retention obligations routinely outlast vendor relationships. If the verifier is a standalone tool that works offline, the evidence keeps its value independently of any commercial relationship.

A certificate is a dated, signed, tamper-evident claim by a named party. It is not a physical law. The engineering makes the claim durable and attributable; it does not make it true.

What it does not prove

That no copy of the key exists.Crypto-shredding renders ciphertext permanently undecryptable by destroying the key — provided the key is genuinely gone. No signature can establish the non-existence of a copy somewhere in the world. What the certificate does is convert a vague question into a precise one: instead of “did you really delete it”, the auditor now asks “show me your key custody and destruction procedure”. That is a far better conversation to be having, and it is still a conversation about process rather than mathematics.

That the data does not exist elsewhere. The certificate scopes to one archive. Copies in a warehouse, an export, a laptop or a third party are outside it. Any vendor whose deletion story never asks where else your data lives is selling you a document, not an outcome.

That the issuer is honest. Here is the uncomfortable core of it: a certificate signed by us attests to our own conduct. It is unforgeable and it is self-interested at the same time. Cryptography guarantees the statement came from us and has not changed; it cannot make us truthful.

The only real answer to that last one

You cannot engineer your way out of self-attestation from the inside. The way out is to stop being the only signer.

If an independent party observes the erasure and countersigns the certificate, the evidentiary weight changes category. It is no longer our word about our own conduct; it is a claim corroborated by someone with no stake in our being right. This is why notaries exist, and why auditors are required to be independent — and it is the direction we are working in, with an external organisation independently verifying our certificates rather than accepting our verifier’s output. We will publish that work jointly when it is finished, including whatever it turns up that we did not expect.

Until then the honest description of a single-signer certificate is: strong, durable, attributable, verifiable by anyone — and issued by an interested party. That is considerably better than a PDF, and it is not the same as independent proof. Anyone in this market who does not draw that distinction for you has an incentive not to.

What to ask for

• A certificate that commits to the subject, the archive, its hash and a timestamp.
• A verifier that runs offline, without the vendor’s systems, and keeps working if the vendor does not.
• A written key-custody and destruction procedure — because that, not the certificate, is what the claim ultimately rests on.
• A straight answer on independent witnessing, and on signature longevity.

Ours ships as part of the Provably-Erasable Archive, and the mechanism behind it is described in deleting one person from an archive you promised never to change. If you find a gap in the reasoning above, that is a useful email to send us.