A system and method for searching and retrieving certificates, which may be used in the processing of encoded messages. In one 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 described herein 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.