Techniques are disclosed relating to secure message exchanges. In some embodiments, a first computing device generates an account key associated with a user account shared by a plurality of computing devices. The first computing device signs a public key of the first computing device with the generated account key to produce a digital signature and sends the public key and the digital signature to a first server system for distributing the public key to a second computing device attempting to send an encrypted message to the first computing device. The first computing device sends the account key to an external storage external usable by others of the plurality of computing devices to obtain the account key and use the account key to sign public keys of the other computing devices. The first computing device receives, from the second computing device, the encrypted message encrypted using the public key.