Seth Schoen's Hard to Verify Signatures

[Hal Finney]

Hi, Adam - Yes, that's interesting.  Seth Schoen's posting and
subsequent blog entries do compare his goals with hashcash and similar
stamp minting systems; where hashcash wants to make minting expensive
and verification easy, Seth's HTV signatures aim to make signing easy
and verifying expensive.

> I think maybe you have observed an additional simplification.  In my
> case I use sender chooses x randomly (actually hash output of random
> value and resource string), and computes y = x^{x^w} mod n as the work
> function (expensive operation); and z = x^w mod phi(n), y =?  x^z mod
> n as the cheap operation (verification).
>
> I think your approach could be applied on the encryption side too
> resulting in simpler, faster verification.  Instead it would be:
>
> x is random, compute y = x^{2^t+1} mod n; verify x =? y^d mod n

The main advantage here I think is that d can be precomputed.  However you
could do the same by using y = x^{2^w} instead of x^{x^w}.  Then you could
precompute z = 2^w mod phi and you would have a single exponentiation
to verify just like in my scheme.  The RSW time-lock-puzzle paper does
it this way, they use 2^w as the exponent where w is the work factor.

Hal

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com