Technically AFAIK, the revocation list could be turned into a Bloom filter (or one of its alternatives) and updated from the servers periodically. edit: on 2nd

Technically AFAIK, the revocation list could be turned into a Bloom filter (or one of its alternatives) and updated from the servers periodically. edit: on 2nd thought just a list of hashed cert ids could suffice because it is hard to imagine there ever being thousands of revocations. That way the provider would have no knowledge of which certs are being verified.