A system is provided that uses cryptographic techniques to support secure messaging between senders and recipients. A sender may encrypt a message for a recipient using the recipient's public key. The sender may send the encrypted message to the message address of a given recipient. A server may be used to decrypt the encrypted message for the recipient, so that the recipient need not install a decryption engine on the recipient's equipment.