Certificates issued by a CA are distributed across multiple CRLs. Each certificate issued by the CA is assigned to a specific CRL, and the address of that CRL is written to the appropriate field of the certificate, such that an authenticating application can subsequently determine if the certificate is revoked. When the CA revokes a specific one of the issued certificates, it determines to which CRL the revoked certificate is assigned, and updates the specific CRL accordingly. In some embodiments, a single one of the multiple CRLs is active for assignment of certificates at any given time, and each certificate issued by the CA is assigned to the currently active CRL. In other embodiments, assignments of issued certificates are distributed between different ones of a pre-determined number of multiple CRLs by applying a statistical distribution formula to each issued certificate to determine a corresponding target CRL.