[16126] in cryptography@c2.net mail archive
Re: Seth Schoen's Hard to Verify Signatures
daemon@ATHENA.MIT.EDU (Adam Back)
Thu Sep 9 00:36:15 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 8 Sep 2004 17:30:51 -0400
From: Adam Back <adam@cypherspace.org>
To: Hal Finney <hal@finney.org>
Cc: cryptography@metzdowd.com, Adam Back <adam@cypherspace.org>
In-Reply-To: <20040908005238.F218C57E2B@finney.org>
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@metzdowd.com
