[Cryptography] Compressed CRLS

Phillip Hallam-Baker phill at hallambaker.com
Wed Oct 15 10:51:20 EDT 2014

Rob Stradling and myself have been looking at the revocation problem
again. Using traditional techniques some CRLs have expanded to 3 MB.
Using a novel compression technique we can create a CRLSet that allows
encoding densities of about 6 bits per revoked certificate.

In practice this means that we can give the status of every unexpired
WebPKI SSL certificate from every public CA in about 170KB. [Rob
scraped the Web and collected up 2.5 Million certs of which 250
thousand were revoked].

Delta CRLsets are also possible, a daily update would be about 5KB.

The asymptotic space requirement (in bits) is |B| (log2 (|A|+|B|))
where A is the set of valid unexpired certs and |B| is the revoked

The compression technique is described here:

Note that IPR claims do apply but it is understood that any
application to the Certificate Revocation problem for the Web would
have to be open source compatible.

The key to efficiency here is that the CRLSet only allows us to
distinguish valid unexpired certs from revoked unexpired certs. While
it gives exact answers for these cases it gives a random answer for
certs that are not in A or B.

The paper describes the simplest approach we came up with. Rob's
improvements double the efficiency.

I will be in Hawaii if anyone wants to talk to me there.

More information about the cryptography mailing list