It turns out my memory of what it's difficult to find square roots modulo
was wrong. The fixed version is below.
Alice wants to force Bob to do w 'units' of computation in such a way that
he can't do the computation in parallel and she can verify the result
expending relatively little resources.
Alice first picks primes p and q, both congruent to 3 mod 4, and finds
their product, N. She will be able to reuse N any number of times so long
as she keeps p and q secret.
For a specific challenge, Alice picks secret value s, less than N. She
then computes
s + 1/s (mod N)
and sends it and N to Bob. Bob can't compute s because that would involve
taking a square root modulo N, which is just as difficult as factoring N.
Alice's challenge to Bob is to compute f(w), where
f(n+1) = (f(n))^2 - 2 (mod N)
and
f(0) = s + 1/s (mod N)
She can compute f(w) quickly using the formula
f(n) = s^(2^n) + 1/(s^(2^n)) (mod N)
which can be easily verified using induction.
To compute s^(2^n) (mod N) quickly, Alice first finds it's value mod p and
mod q. To find s^(2^n) mod p, she first computes
e = 2^n (mod p-1)
and then computes s^e (mod p), which is equal to s^(2^n) (mod p) because
of the basic number theory theorem
s^(p-1) = 1 (mod p)
Not only does this method prevent Bob from doing parallel computation, it
allows Alice to control very precisely the amount of work he must perform.
Public key techniques always feel guided by an unseen hand. There is
clearly an underlying theory we have yet to discover.
-Bram Cohen
