A secure communication system wherein message decryption may be performed while off-line, or optionally while on-line. A sender encrypts a message based on the message key and sends it to the recipient. An envelope containing a message key is created by encrypting the message key based on a verifier, where the verifier is based on a secret of the recipient. The recipient is provided the envelope, along with the message or separately, from the sender or from another party, contemporaneous with receipt of the message or otherwise. The recipient can then open the envelope while off-line, based on their secret, and retrieve the message key from the envelope to decrypt the message. In the event the recipient cannot open the envelope, optional on-line access permits obtaining assistance that may include obtaining an alternate envelope that the recipient can open.