Providing information about digital certificate validity includes obtaining a plurality of signing key/verification key pairs, where each signing key provides a digital signature and a corresponding one of the verification keys verifies the digital signature and where digitally signing together a plurality of data elements using the signing keys is computationally more efficient than digitally signing each of the data elements individually, ascertaining digital certificate validity status for each certificate in a set of digital certificates, generating a plurality of artificially pre-computed messages about the validity status of at least a subset of the set of digital certificates, and digitally signing together the artificially pre-computed messages using signing keys from the pairs. Ascertaining digital certificate validity status may include obtaining authenticated information about digital certificates. The authenticated information about digital certificates may be generated by an entity that also revokes certificates. The authenticated information about digital certificates may be a CRL. The artificially pre-computed responses may be OCSP format responses.
