I want to implement a service that can't read the data you store there.
The Idea is that I, like in a password manager, use the password to derive a vault key, which is different from the authentication key, that is used to encrypt/decrypt the data.
How can I encrypt and store data from multiple devices while only sharing the vault key in a way that allows new devices to join while all others are offline and while ensuring that no security issues arise from IV reuse in a setting where the client is unable to trust the server?
I cannot use the vault key directly because I can't know which IVs can be used when logging in from a new device, this creates the danger of IV reuse. When creating the IVs randomly, NIST recommends a strict limit of 2^32 encryptions per key, this feels a little too low for me. I can't trust the server with this either, so I must not rely on the server to generate/send the next fixed field to use as it might just send the same message to multiple devices.
One Idea I have would be to generate a key for each device on its own and store those keys, encrypted with the vault key, on the server (for other devices to be able to decrypt the data), and the IVs stay on the devices locally. Each package then would then need know which key is needed to decrypt it, but this feels like a reasonable compromise to me. I would have to think about what to do when the user changes the password, but I think I just encrypt the previous vault key with the new one and send it to the server ..
Is there a (better) way to share the vault-key-nonce between multiple devices in a way that no nonce is used twice without trusting the server with anything?