In article <[EMAIL PROTECTED]>,
Bram Cohen <[EMAIL PROTECTED]> wrote:
> The problem is to find a form of hashcash which can't be paralellized.
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
In particular, the above paper suggests that Alice should construct a
RSA modulus n, pick a random s, and ask Bob to calculate s^{2^t} mod n.
This may be done in polylog time on Alice's end, but for Bob it seems to
require O(t) work, and parallelization does not seem to help.
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?
P.S. Your scheme has a technical flaw. You'll want to work mod n, a
RSA modulus, rather than mod p, a prime. Square roots mod p are easy.
