Authentication via revocable signatures

A computer program product for authenticating a message, via a revocable signature at a signing computer, to a verifier computer, said computer program product comprising a computer readable non-transitory storage medium having program instructions embodied therein, the program instructions being executable by the signing computer to cause the signing computer to:

• generate first auxiliary data and second auxiliary data respectively dependent on a public key and a private key of a public-private key pair for the message;
• hash the message and the first auxiliary data via a chameleon hash algorithm, using a public hash key of the verifier computer, to produce a first hash value;
• sign the first hash value, using a secret signing key of the signing computer, to produce a signature;
• and send the message, the signature and the first auxiliary data to the verifier computer, and store the second auxiliary data.

A system for authenticating a message, the system comprising a signing computer and a verifier computer, wherein the signing computer is adapted to authenticate the message to the verifier computer via a revocable signature by:

• generating first auxiliary data and second auxiliary data respectively dependent on a public key and a private key of a public-private key pair for the message;
• hashing the message and the first auxiliary data via a chameleon hash algorithm, using a public hash key of the verifier computer, to produce a first hash value;
• signing the first hash value, using a secret signing key of the signing computer, to produce a signature;
• sending the message, the signature and the first auxiliary data to the verifier computer, and storing the second auxiliary data;
• wherein the verifier computer is adapted, in response to receipt of the message, the signature and the first auxiliary data, to check whether the second auxiliary data corresponding to the first auxiliary data has been published, and if so, rejecting the signature, and if not, hashing the message and the first auxiliary data via said chameleon hash algorithm using said public hash key to produce a second hash value;
• and
• using a public signing key of the signing computer to check validity of said signature with respect to the second hash value.