A method and apparatus constructs a preferred certificate chain, such as a list of all certificate authorities in a shortest trusted path, based on generated certificate chain data, such as a table of trust relationships among certificate issuing units in a community of interest, to facilitate rapid validity determination of the certificate by a requesting unit. In one embodiment, requesting units, such as certificate validation units or subscribers, send queries to a common certificate chain constructing unit. Each query may identify a beginning and target certification authority in the community. The certificate chain constructing unit then automatically determines the certification chain among certification issuing units between the beginning and target certification authorities for each query and provides certificate chain data to the requesting unit. The requesting unit then performs validity determination on the certificate to be validated based on the certificate chain data.