A signature authority generates revocable one-time-use keys that are able to generate digital signatures. The signature authority generates a set of one-time-use keys, where each one-time-use key has a secret key and a public key derived from a hash of the secret key. The signature authority generates one or more revocation values that, when published, proves that the signature authority has the authority to revoke corresponding cryptographic keys. The signature authority hashes the public keys and the revocation values and arranges the hashes in a hash tree where the root of the hash tree acts as a public key of the signature authority. In some implementations, the one-time-use cryptographic keys are generated from a tree of seed values, and a particular revocation value is linked to a particular seed value, allowing for the revocation of a block of one-time-use cryptographic keys associated with the particular seed.