Seth Schoen's Hard to Verify Signatures

Adam Back adam at
Wed Sep 8 17:30:51 EDT 2004


I proposed a related algorithm based on time-lock puzzles as a step
towards non-parallelizable, fixed-minting-cost stamps in section 6.1
of [1], also Dingledine et al observe the same in [2].

The non-parallelizable minting function is in fact the reverse: sender
encrypts (expensively) and the verifier encrypts again (but more
cheaply) and compares, but I think the relationship is quite analogous
to the symmetry between RSA encryption and RSA signatures.

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

I'll add a note about that when I get around to updating it next.


[1] Hashcash - Amortizable Publicly Auditable Cost-Functions

[2] Andy Oram, editor.  Peer-to-Peer: Harnessing the Power of
Disruptive Technologies. O'Reilly and Associates, 2001.  Chapter 16
also available as

On Wed, Sep 08, 2004 at 11:48:02AM -0700, "Hal Finney" wrote:
> Seth Schoen of the EFF proposed an interesting cryptographic primitive
> called a "hard to verify signature" in his blog at
> An alternative is based on the paper, "Time-lock puzzles and
> timed release Crypto", by Rivest, Shamir and Wagner, from 1996,
> [...]
> Choose the number of modular squarings, t, that you want the
> verifier to have to perform.  [...] you will sign your value using
> an RSA key whose exponent e = 2^t + 1.  > The way you sign, even
> using such a large e, is to compute phi = (p-1)*(q-1) and to compute
> e' = e mod phi, which can be done using about 30 squarings of 2 mod
> phi.  You then compute the secret exponent d as the multiplicative
> inverse mod phi of e', in the standard way that is done for RSA
> keys.  Using this method you can sign about as quickly as for
> regular RSA keys.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list