Nonces don't need to be secret. You can just use a counter value if you want, unencrypted. It gets harder when you have many uncoordinated senders. You can shar

Nonces don't need to be secret. You can just use a counter value if you want, unencrypted. It gets harder when you have many uncoordinated senders. You can shard your nonce-space; give each sender a unique prefix, but this reduces the number of messages they can each send with the same key. Bigger services, such as Public Cloud providers (I work at AWS, and it's a factor for us) actually end up running up on these limits.