A system and method for searching and retrieving certificates, which may be used in the processing of encoded messages. In one embodiment, a certificate synchronization application is programmed to perform certificate searches by querying one or more certificate servers for all certificate authority (CA) certificates and cross-certificates on the certificate servers. In another embodiment, all certificates related to an identified certificate are retrieved from the certificate servers automatically by the certificate synchronization application, where the related certificates comprise at least one of one or more CA certificates and one or more cross-certificates. Embodiments of the invention facilitate at least partial automation of the downloading and establishment of certificate chains, thereby minimizing the need for users to manually search for individual certificates.