A MIME or XML formatted message is stored and a map is processed in place of a message. The map is a compact representation of the message. The map is indicative of the content and structure of the message. The map comprises tags that map to and are indicative of portions of the message. When a portion of the message is to be accessed, the associated tag in the map is processed to determine the location of the associated portion of the message, and the associated portion of the message is accessed at the location. To allow accurate decryption of signed messages, the format of the message is preserved.