A method and system for server-based encrypted messaging that uses a receiver-determined password to symmetrically encrypt messages that are intended for that receiver. A sender authenticates to a Recipient Password Server in order to generate a message and optionally to upload attachments, which are enclosed in a virtual envelope that is digitally signed. Each envelope is encrypted with the intended recipient's password and sent either as an email attachment or by other messaging protocol. Messages intended for multiple recipients are each custom encrypted with the individual recipient's password and mapped to the correct identity and reception point. Users can change their passwords at any time. A method is also included to support secure searches of a collection of encrypted envelopes for exact words and phrases.