A method for enforcing use of certificate revocation lists in validating certificates, the lists being associated with a series of list generation indices such that each list is assigned one index which advances according to a time of generation of the list, the lists and the indices being cryptographically signed, the method including receiving one of the lists and an associated index as an identifier of the one list, checking the certificates against the list, associating each of the certificates, which have been checked against the list, with the index, receiving an enforcement generation index (EGI) associated with a latest list in use, storing the EGI as a last known EGI, and refusing performance of an action associated with a certificate if the one index of the one certificate is earlier in the series than the last known EGI. Related apparatus and methods are also included.