Seth Schoen's Hard to Verify Signatures

[Major Variola (ret)]

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..