Can a large corporation make a believable promise
However, if the third party makes a secret copy, then they can covertly sell it for large amounts of money.
The thing about this is when it comes to a pivotal and highly-valued asset such as said key, it should never be,
- created
- transmitted
- kept
- deleted
by a third-party vendor. These processes if possible should be done internally.
Let's say if you would want to task a third-party vendor to delete said assets, it should be done with automation and limit that human/employee interaction, or keep it to the bare minimum.
Another solution would be, another layer of encryption on this already encrypted key. So that even if the vendor would to lay their eyes on this key, it wouldn't mean much to them, only your organization can see it, but this kinda deems the purpose of the third-party vendor a tad bit redundant.
Companies make promises they can't renege on all the time - that's what a contract is. After all, insurance wouldn't exist if an insurer could wriggle out of paying claims through things like secret policies.
That's not to say you can't breach a contract - of course you can, things go to court all the time. But a contract is as binding as anything you can do with directors and shareholders passing resolutions, and would need equally careful drafting.
The weaknesses of contracts in this situation are:
The courts can't put the toothpaste back in the tube (and compensation may not be sufficient for your situation)
The courts can't deal with things that are undetectable
As such applications with serious needs will often call for public transparency, hardware security modules, witnesses from multiple organisations, certifications from audit firms, and suchlike.
How could the company show that it instructed the employees to destroy the key?
Easy. When an employee was instructed, he/she signs a document that he/she was instructed and understood fully the requirements.
But from the point of view of security this is absolutely useless.
- Some employees can violate it intentionally. In many cases it is almost impossible to find out who did it.
- Some employees can forget to do some important steps.
- Some employees can misunderstand some instructions and violate them, believing they do everything right.
- It is very hard and very expensive to implement this technically. Each file on a disk can be moved many times from one place on the disk to another one. Information on the disk may remain recoverable. It is expensive to make sure it is not recoverable.
- For storing of important information reliably often RAID disks are used. One of such disks could have been replaced. One would need to search for it and make sure it doesn't contain your key.
- The key could have been copied to other devices many times, intentionally or not. E.g. many companies apply regular automated backups. Such key file could have been put to many backups. Important backups are normally distributed to several remote data centers (e.g. one in US, one in Europe, one in Australia).
- Such backups are stored on their disks. Means one would need to determine all drives involved and clean them properly or destroy them.
TLDR: No matter who and what promises, there is no way to guarantee that your key is not recoverable.
Solution: Don't share your secrets with others, or accept that from now on they will always know your secrets. You can withdraw physical objects, but there is no way to "withdraw" information.