Seth Schoen's Hard to Verify Signatures

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


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.

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



More information about the cryptography mailing list