A system is provided that uses identity-based encryption (IBE) to allow a sender to securely convey information in a message to a recipient over a communications network. IBE public key information may be used to encrypt messages and corresponding IBE private key information may be used to decrypt messages. Information on which IBE public key information was used in encrypting a given message may be provided to the message recipient with the message. Multiple IBE public keys may be used to encrypt a single message. A less sensitive IBE public key may be used to encrypt a more sensitive public key, so that the more sensitive public key can remain hidden as it is sent to the recipient.