A recipient device 825-1 may submit a recipient public key upload 910 to the key servers 243 of the messaging system 750. The recipient public key upload 910 may be performed during an initial configuring of a messaging application 830 to configure the messaging system 750 with public keys for distribution to other client. The recipient public key upload 910 may be performed occasionally to refresh the pool of public keys available to the messaging system 750 for distribution to client devices looking to contact the recipient device 825-1. The recipient public key upload 910 may comprise a plurality of public keys to which the recipient device 825-1 has the corresponding private key which it keeps secret in a repository on the recipient device 825-1. This may generally be performed by all the client devices using the messaging system 750 to empower the messaging system 750 to assist other client devices in engaging in secure communication. The key servers 243 may store a plurality of public keys received in the recipient public key upload 910 in a key store. The recipient device 825-1 may associate each of the plurality of public keys in the recipient public key upload 910 with a public key identifier for use in identifying which of the public keys was used by a sender device to encrypt a message sent to the recipient device 825-1.