In an example, a computing device is described. The computing device comprises a communication interface and a processor. The processor is to determine whether a signature, produced by a signer, is derived from a free state under a stateful signature scheme. The free state is a state that has not been used as an input to generate a signing key. The signature is encrypted by the signer. The processor is further to, in response to determining that the signature is derived from a free state, decrypt the encrypted signature. The processor is further to transmit the decrypted signature to a recipient via the communication interface.