A system and method for associating message addresses with certificates, in which one or more message addresses are identified and associated with a user-selected certificate that does not contain any e-mail addresses. In certain situations, a message may be encrypted using a certificate that does not contain an e-mail address that matches the e-mail address of the individual to which the message is to be sent, 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 are saved in a data structure that resides in a secure data store on a computing device, such as a mobile device.