A system and method for processing messages with encryptable message parts. When constructing an encoded message, an encryption key of a plurality of identified encryption keys is used to encrypt message data of a message part. A key identifier is associated with the message part and identifies the encryption key used for the encryption of the message data of the message part. In at least one exemplary embodiment, encryption keys that are used to encrypt message data of message parts are provided in a separate message part, arranged by key identifier. In particular, the encryption keys, arranged by key identifier, may be provided in exactly one message part separate from the message parts containing message data. This allows for a compact message encoding.