A few weeks ago I posted some hashcash ideas which turned out to be almost identical to the ones in http://theory.lcs.mit.edu/~rivest/RivestShamirWagner-timelock.ps To try and save face I've come up with some tricks which allow a standard modulus to be used. If somebody can see how to break these or they're already known please tell me and I'll crawl back into my cave again. First, Alice finds p and q, both prime, and publishes N=pq. She also computes E=2^(10^6) (mod phi(N)) and publishes that as well. I don't believe that this helps anyone compute p and q. If it does, both of these techniques are completely broken. In the first technique, Bob would like to issue a challenge to Carol. To do this, he picks s, a random number mod N, then brings it to the E power k times, where k is proportional to the amount of work he wants Carol to have to do, resulting in the number m. He then writes down m+1/m (mod N) and sends s+1/s and k to her. Carol then repeatedly squares and subtracts 2 from the number he sent her a total of k * 10^6 times and sends the result back to him. Bob then verifies that the result is, in fact, equal to m+1/m In the second technique, Bob would like to prove to Carol that he did some work to Carol without having to get a challenge from her beforehand. To do this, he takes a message he wants to prove he mulled over and hashes it, then squares the result repeatedly (mod N) a total of 10^6 - 1 times, and sends his message and the result to Carol, who takes the hash to the E power and verifies that it's equal to the value Bob sent her squared (mod N). This technique can be made to work for work factors greater than 10^6 by taking the hash of one bit of work and including it in the next repeatedly, but that results in a much larger proof of work than the constant-sized one the previous technique does. Well, that's all I could come up with. Any thoughts/criticisms are welcome. -Bram Cohen
