A method, system, and service of authenticating a public key certificate for a relying party (RP). A Certificate Authority (CA), who issued the certificate, is a member of a Public Key Infrastructure (PKI) having a Certificate Policy (CP). First quality levels required of the CA by the RP are accessed by a certificate classification service (CCS) and corresponding second quality levels possessed by the CA are ascertained by the CCS. At least one quality characteristic pertaining to the second quality levels relates to at least one element of the CP. The ascertained second quality levels are compared by the CCS with the corresponding accessed first quality levels. A result of the comparing, communicated by the CCS to the RP, is that the certificate is authenticated if the comparing has determined that each first quality level is not less than each corresponding second quality level.