A system and method for associating message addresses with certificates, in which one or more secondary message addresses are identified and associated with a user-selected certificate. The secondary message addresses are saved in a data structure that resides in a secure data store on a computing device, such as a mobile device. When a message is to be encrypted and sent to an individual using a particular certificate, an address mismatch would not be detected so long as the address to which the message is to be sent matches any of the message addresses associated with the certificate. The message addresses associated with the certificate include any message addresses contained within the certificate itself (“primary message addresses”) as well as any secondary message addresses that have been subsequently associated with the certificate.