[16127] in cryptography@c2.net mail archive
Re: Seth Schoen's Hard to Verify Signatures
daemon@ATHENA.MIT.EDU ("Hal Finney")
Thu Sep 9 00:37:32 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
To: adam@cypherspace.org
Cc: cryptography@metzdowd.com
Date: Wed, 8 Sep 2004 15:08:00 -0700 (PDT)
From: hal@finney.org ("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@metzdowd.com
