In a computer-implemented method for signing a message by a user device of a public key infrastructure (PKI) system, the message and a user public key are sent to at least one attestation server and a server signature on the message is received from the attestation server. The server signature attests the validity of the user public key and is bound to the user public key and the message. The message and the server signature are signed with a user private key, thereby providing a user signature on the message. An attestation server and a related computer program product are also provided.