A method and device are useful for enabling a trust relationship using an unexpired public key infrastructure (PKI) certificate, where a current status of the PKI certificate is unavailable. The method includes determining at a relying party that a certificate status update for the PKI certificate is unavailable (step 905). Next, in response to the certificate status update being unavailable, a tolerable certificate status age (TCSA) for the PKI certificate is determined at the relying party based on one or more attributes associated with a certificate holder of the PKI certificate (step 910). Using the PKI certificate, a trust relationship is enabled between the relying party and the certificate holder after determining the TCSA and before an expiration of the TCSA (step 915).