A certification authority (CA, 120) generates decryption key data (K'.sub.Fj) for each set (F) in the complement cover (804) for a plurality of digital certificates. The CA encrypts all or a portion of the validity proof data (c.sub.j(i)) for each digital certificate (140.i) for each time period j for which the validity proof is to be provided. For each certificate, the decryption can be performed with decryption keys (K.sub.ij) that can be obtained from the decryption key data (K'.sub.Fj) for any set containing the certificate. The CA distributes the encrypted portions of the validity proof data to prover systems that will provide validity proofs in the periods j. To perform certificate re-validation in a period j, the CA constructs the complement cover for the set of the revoked certificates, and distributes the decryption key data (K'.sub.Fj) for the sets in the complement cover. In some embodiments, for each period j, the decryption keys (K.sub.ij) are also a function of the decryption key data provided for the preceding periods of time. Therefore, to perform the re-validation, the CA constructs the complement cover not for the set of all the revoked certificates but only for the set of the certificates revoked in the previous period j-1. The complement cover size can therefore be reduced. Other features and embodiments are also provided.