A secure electronic messaging system permits communication between registered users, with the assistance of a key server. The system requires a recipient to submit key retrieval information to a key server, and obtain decryption key information. The decryption key information is necessary for the recipient to form the decryption key which is used to read a message encrypted by the sender. The decryption key information may be an encrypted version of a decryption key, or portions thereof, or may be portions of an unencrypted version of a decryption key, among others. Typically, the key retrieval information may either be sent to the recipient by the sender, or may be generated by the recipient, based on information sent by the sender.