Secure bulk messaging mechanism in which, roughly described, a sender first encrypts a message once. The message can be decrypted with a message decryption key. These can be symmetric or asymmetric keys. For each recipient, the sender then encrypts the message decryption key with the recipient's public key. The sender then sends the encrypted message and the encrypted message decryption keys to a store-and-forward server. Subsequently, one or more recipients connect to the server and retrieve the encrypted message and the message encryption key that has been encrypted with the recipient's public key. Alternatively, the server can forward these items to each individual recipient. The recipient then decrypts the encrypted message decryption key with the recipient's private key, resulting in an un-encrypted message decryption key. The recipient then decrypts the message using the un-encrypted message decryption key.