A method and device are useful for enabling a trust relationship using an expired public key infrastructure (PKI) certificate. The method includes determining at a relying party a maximum permissible grace period during which the PKI certificate can be conditionally granted a valid status (step 905). Next, at the relying party an uncertainty interval is determined, during which the relying party is unable to detect a revocation of the PKI certificate (step 910). A certificate grace period is then determined at the relying party from a function of the maximum permissible grace period, the uncertainty interval and at least one attribute defined in the PKI certificate (step 915). Using the PKI certificate, a trust relationship is then enabled between the relying party and a certificate holder of the PKI certificate, after determining the grace period and before an expiration of the grace period (step 920).