Hard-to-verify signatures
Usually cryptographers try to come up with signatures that are efficient to compute and efficient to verify. That is, they want to find a function F(m) over a message and a function V(F(m),m) that produce a signature and determine whether a signature is valid such that F and V are both simple to calculate.
Today I was wondering if anyone has created a signature technique that is efficient to compute but hard (though not impossible) to verify. That is, F should be simple to calculate but V should be difficult to calculate. I have a particular application in mind, but I don't know if anyone has actually tried to create this sort of signature.
I guess one technique would be add a salt to the message that is to be signed, but not disclose what the salt was. That is, instead of computing F(m), you would compute F(m,s) where s is a relatively small randomly chosen number. A verifier would have to guess which value of s you used in order to see whether the signature was valid, and that guessing process could consume a lot of time. By varying the size of the salt, you could influence the amount of time it takes to verify the signature.
For example, if I wanted to sign m, I could generate some s, pad m to a fixed length, append s, and then compute the SHA-1 hash of the concatenated m, padding, and s, and then compute an RSA signature over that SHA-1 value. I could publish m and the RSA signature and the length of s, but not the value of s. If there's nothing about RSA or SHA-1 that reduces the security of this scheme, it would take an average of about 2^(len(s)-1) RSA signature verifies and an equal number of SHA-1 hash operations in order to verify this signature. But it would only take a single SHA-1 and a single RSA signature to create it.
Here's a PGP message slightly corrupted and then signed with my key 0167ca38 to illustrate this technique:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Signatures that are inefficient to verify could be more useful for some applications than signatures that are efficient to verify. Three undisclosed decimal digits follow below, but have been replaced with exclamation points in the published version of this message. !!! -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (GNU/Linux) iD8DBQFBN/WaVrAxXwFnyjgRAtjyAJ9hoZ746cRjHS5NS3wRH5q5bdFY9ACfS1q4 v62MTLblSZfN1ecmqd/S09w= =VSDz -----END PGP SIGNATURE-----
It seems as if this would actually work. On average, you would have to try about 500 times to find out whether this signature is actually valid. (If you do this, let me know!) If the hash used for signing is secure, this technique isn't much help for an attacker trying to forge signatures or alter signed messages. And it didn't take me appreciably longer to generate this signed message than it normally takes me to generate any other signed message.
