Hi 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. Adam [1] Hashcash - Amortizable Publicly Auditable Cost-Functions http://www.hashcash.org/papers/amortizable.pdf [2] Andy Oram, editor. Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O'Reilly and Associates, 2001. Chapter 16 also available as http://freehaven.net/doc/oreilly/accountability-ch16.html. 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.