> You left out b) vendor has the keys stolen or leaked by a disgruntled employee and now the encryption is useless.
e) If the keys are stolen, issue new keys to all devices
The leaked keys are only good for physically compromised devices in the hands of people with access to the scanning electron microscopes, which I daresay is an extremely small attack surface.
There is only a small window after the leak in which a device can be stolen, powered down, and compromised.
On the other hand, you could mandate that such keys aren't allowed to be stored in databases (physical access only)
You don't always know that keys have been stolen. And an electron scanning microscope is hard to get now, but what about state-sponsored actors spending half a decade developing a pocket-sized tool? The whole point of E2E is that all of these scenarios are literally not possible.
Well, periodically reissue keys then regardless of if you think they've been compromised. Or don't store the private key in a database, store on physical media in a vault that is airgapped and hard to access. Make the read-only-ability of the storage chip more difficult and onerous with each generation like paper currency security.
My point it that you could make it so difficult to break E2E for even the most elite hackers that the only realistic way to do it is with a warrant.
Not if you're sponsored by a hostile actor with functionally limitless resources. E2E isn't just about stopping legitimate law enforcement from conducting investigations.
The more realistic scenario is already possible today, and doesn't need to involve so much technical mumbo-jumbo: at step #2, instead of stealing your phone, they kidnap you, and torture you until you give up your password. Done, and no need for steps 3-5.
(And I suspect, for a sufficiently-motivated state-level actor, that actually falls under "easy", or at most "medium".)
> We've seen this happen with TLS certificate authorities
Have we? I'm going to assume that you mean CAs in the Web PKI and not just "My friend Bob runs TLS and this has happened to the CA he was running on his Windows 10 laptop".
The last CA where we had a really grave problem was DigiNotar, in 2011. It seem _very_ unlikely that the problem at DigiNotar was full key compromise, instead bad guys appear to have penetrated the issuance infrastructure. This means they were able to (and did) issue themselves arbitrary certificates, but it did not give them the actual keys as you've said "happens frequently".
Since then we've seen a variety of unacceptable behaviour, including issuing backdated certificates to conceal the (also problematic) choice to continue doing something that was no longer allowed in new certificates, and issuing "test" certificates which would have been trusted by real client software even though their contents were known to be false. All unacceptable, and all having consequences (for example Symantec is no longer a CA) but all far short of "vendor has the keys stolen or leaked by a disgruntled employee".
e) If the keys are stolen, issue new keys to all devices
The leaked keys are only good for physically compromised devices in the hands of people with access to the scanning electron microscopes, which I daresay is an extremely small attack surface.
There is only a small window after the leak in which a device can be stolen, powered down, and compromised.
On the other hand, you could mandate that such keys aren't allowed to be stored in databases (physical access only)