Let's say that I sign someone's key and then later decide that was a bad idea - either it was a bad idea at all, or I should have signed it with a different level of trust. Is it possible, both in a theoretical and also in a practical way, to "un-sign" someone else's key?
Removing a Local-Only Signature
If the signature is still only kept locally (either by never sending it to anybody or the key servers, or by even having performed an
Revoking Published Signatures
If a signature was already sent to the key servers, you still can delete it locally, but you will not be able to remove anything from the key servers. The OpenPGP key server infrastructure is designed not to delete/forget anything, to be resistant against deletion attacks (where the attacker wants to remove eg. your key).
Instead of deleting the signature, now revoke it. This time, run
Now you should upload the revocation certificate (which more or less states "This certificate invalidates the signature I made starting from a given date for the reason given") to the key servers by running
As soon as the revocation sync'd throughout the key servers (some minutes) and other users will update key
You can't unsign, but you can revoke your signature on their key. Once someone has synced both the original signature and the revocation, their UI should show both and will no longer use the signature in trust calculations. To do this with GnuPG: