Può capitare che a una persona venga rubata, o la persona smarrisca, la propria chiave privata. In questo caso non è più vero quanto attestato dal certificato, non è più vero che il certificato contiene la chiave pubblica corrispondente alla chiave privata di una certa persona. In questo caso il certificato deve essere dichiarato non più valido. Il metodo con cui i certificati vengono dichiarati non più validi è quello di includerli in una lista chiamata CRL. La CRL è la lista dei certificati revocati, ossia dei certificati non più validi. Le CRL sono numerate, anzi gli viene attribuito una data, questa è la CRL del 30 settembre del 1999 e dice che il certificato numero 104 non è più valido a partire dal 25 aprile 1998, perché si è rotta la smart-card entro cui la chiave privata era contenuta. Invece il certificato 97 non è più valido a partire dal 30 agosto 1999, a causa di un furto del portatile che conteneva la chiave privata. Per evitare che qualcuno emetta delle CRL false, anche la CRL viene firmata dalla autorità di certificazione che ha emesso la CRL. Si noti che l'autorità di certificazione agisce in modo abbastanza piratesco, nel senso che l'autorità di certificazione emette questo elenco di certificati non più validi, ma demanda agli utilizzatori dei certificati il controllo. Ogniqualvolta si riceve una firma digitale accompagnata da un certificato a chiave pubblica, è compito di chi riceve questa firma andare a verificare che il certificato associato sia ancora valido, ossia non sia inserito all'interno di una lista di certificati revocati.