Seth Schoen's Hard to Verify Signatures
Hal Finney
hal at finney.org
Wed Sep 8 18:08:00 EDT 2004
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
More information about the cryptography
mailing list