[6853] in cryptography@c2.net mail archive
Re: A non-parellelizable form of hashcash
daemon@ATHENA.MIT.EDU (Bram Cohen)
Mon Mar 27 08:14:48 2000
Date: Sun, 26 Mar 2000 19:59:42 -0800 (PST)
From: Bram Cohen <bram@gawth.com>
To: "David A. Wagner" <daw@cs.berkeley.edu>
Cc: cryptography@c2.net,
People who supposedly write code <coderpunks@toad.com>
In-Reply-To: <8bma6d$45o$1@blowfish.isaac.cs.berkeley.edu>
Message-ID: <Pine.LNX.4.10.10003261912290.14729-100000@ultra.gawth.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
On 26 Mar 2000, David A. Wagner wrote:
> Your technique appears to be a more complicated -- but closely
> related -- variant of the construction given in the following paper:
> ``Time-lock puzzles and timed-release Crypto'', R. Rivest,
> A. Shamir, and D. Wagner, MIT LCS tech report TR-684, February 1996.
> http://www.cs.berkeley.edu/~daw/papers/timelock.ps
Yep, that it is. I'm a little embarassed for not having already known
about that one.
> I'm not sure if there is any reason to prefer either scheme over the
> other on security grounds. If the two have equivalent security, then
> the simplicity of the RSW construction looks appealing. Any thoughts
> on the two schemes' relationship?
I figured out the simpler construction, but for some reason thought it was
insecure, so I came up with the more complicated one.
I suspect that there are the equivalent of chosen plaintext and ciphertext
attacks against the simpler scheme - that is, if Alice acts as an oracle
for computing a^(2^b), then Bob can find p and q. This would imply that
the more complicated technique is (marginally) more secure. There's no
obvious way of factoring n using the oracle though.
Other than that, they look about the same - there wouldn't be any
noticeable difference in performance between the two algorithms.
Mostly I just find the mess which the expansion of f(x)^2 - 2 becomes
after a few iterations very comforting.
-Bram Cohen
