At 11:48 AM 9/8/04 -0700, Hal Finney wrote:

Seth Schoen of the EFF proposed an interesting cryptographic primitive called a "hard to verify signature" in his blog at http://vitanuova.loyalty.org/weblog/nb.cgi/view/vitanuova/2004/09/02 . The idea is to have a signature which is fast to make but slow to verify, with the verification speed under the signer's control. He proposes that this could be useful with trusted computing to discourage certain objectionable applications.

The method Seth describes is to include a random value in the signature

but not to include it in the message. He shows a sample signature with 3 decimal digits hidden. The only way to verify it is to try all possibilities for the random values. By controlling how much data is hidden in this way, the signer can control how long it will take to verify the signature.

This could be called a "salt-free" algorithm :-) Basically its like the problem that a salted-password cracker has to solve when the salt has to be guessed. As far as a modexp() solution, I suggest this, which is as far as I can tell different from what you reference: In an RSA cryptosystem the public exponent is typically low, often 3 or 65537 (for efficiency reasons only a few bits are set; the other constraint is that your message, raised to that power, wraps in your modulus, which makes 65537 a little better). The private exponent is big. Therefore, traditional encryption is "fast", and decryption is slow; the reverse is that signing is slow, verifying a signature is fast. This can be used to achieve Seth's required "fast to make, slow to verify". To achieve the required "user-controllable", the user gets to set the number of bits in the modulus. One might have to use extraordinarily long moduli (making 4Kbits look puny), depending on the time-scale of "slow" and "fast", but so what, primes are free :-) and might even be re-used. If this passes group-muster pass it on..