  We study digital signatures with revocation capabilities and show two
results. First, we define and construct digital signatures with revocable
signing keys from the LWE assumption. In this primitive, the signing key is a
quantum state which enables a user to sign many messages and yet, the quantum
key is also revocable, i.e., it can be collapsed into a classical certificate
which can later be verified. Once the key is successfully revoked, we require
that the initial recipient of the key loses the ability to sign. We construct
digital signatures with revocable signing keys from a newly introduced
primitive which we call two-tier one-shot signatures, which may be of
independent interest. This is a variant of one-shot signatures, where the
verification of a signature for the message ``0'' is done publicly, whereas the
verification for the message ``1'' is done in private. We give a construction
of two-tier one-shot signatures from the LWE assumption. As a complementary
result, we also construct digital signatures with quantum revocation from group
actions, where the quantum signing key is simply ``returned'' and then verified
as part of revocation.
  Second, we define and construct digital signatures with revocable signatures
from OWFs. In this primitive, the signer can produce quantum signatures which
can later be revoked. Here, the security property requires that, once
revocation is successful, the initial recipient of the signature loses the
ability to find accepting inputs to the signature verification algorithm. We
construct this primitive using a newly introduced two-tier variant of tokenized
signatures. For the construction, we show a new lemma which we call the
adaptive hardcore bit property for OWFs, which may enable further applications.
