A system is provided that allows users to communicate securely. A key management service may generate a single public-key/private-key pair. A sender who desires to send a secure message to a receiver may encrypt the message using a message key. The sender may use the public key to encrypt the message key and policy information that dictates how the message may be accessed. The receiver may pass the public-key-encrypted message key and policy information to the key management service. The key management service decrypts this information using the private key. After the key management service uses the policy information to verify that the receiver is authorized to access the message, the key management service may provide the decrypted message key to the receiver. The receiver may use this unencrypted version of the message key to decrypt the message-key-encrypted message from the sender.