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
