It seems plausible that the protocol could be designed such that the device doesn’t know the recovery key. The key serves three purposes: (a) identifying the backup when a user tries to restore it, (b) authenticating that user to the restore API, and (c) allowing the user to decrypt the backup.

(a) is much simpler if there is a fixed identifier of a user, but that identifier doesn’t need to be the entire key or even part of it — it could be some derived material.

(b) isn’t strictly required but I would be very uneasy about allowing anyone who stole a user’s device to download even the ciphertext of that user’s future chats. Also, there’s an obvious issue that even the ciphertext reveals something about the amount of activity from the user.

(c) requires that the restoring user hold something like a private key, that said key can be derived using the restore code, and that the user’s device does not know the private key.

One straightforward-ish solution would be for the user’s device to generate, once, a key pair, a user ID, and a backup API key. (The ID and API key could be generated server-side.). The restore key is (user ID, private key). The device retains (user ID, API key, public key). To upload backups, the device establishes a secure session, sends the user ID, proves knowledge of the API key, uploads a backup, and receives a new API key. The old API key is revoked.

This means:

1. The device does not retain the ability to download future backups.

2. A clone of a device (say id the device leaks its secrets somehow) cannot be used to upload new backups on an ongoing basis without being noticed because of the API key rotation.