[cryptography] High-AT proof-of-work

Elias Yarrkov yarrkov at gmail.com
Fri Jan 18 22:36:21 EST 2013

I was thinking of the problem of high-AT proof-of-work at some point, and I
came up with this scheme. It's only high-AT for the client. The client must
find a collision in a function, but she apparently cannot efficiently use
cycle-finding. That's how it's supposed to be, anyway. :)

The challenger's private key is sufficiently large safe primes p, q.
The public key is n=pq.

AT is O(2^b) or so.

Given (random) g, find b-bit x and y (x != y) so that
    h(g^(2^x) mod n) = h(g^(2^y) mod n)

h is a "hash" that returns b bits. Doesn't need to be very strong. Truncation
might be enough, but it's a bit too neat. For example, XOR every b-bit chunk.

Without the private key, computing g^(2^k) mod n is seemingly not cheaper than
k squarings. Thus, cheap memoryless collision techniques don't seem to work.

The client needs to do about 2^(b/2) squarings and store about 2^(b/2) values
before finding a collision. Or, do 2^b squarings while storing just 1 value. Or
some other tradeoff.

x and y could be shorter. Slightly over b/2 bits is enough.

The challenger can compute g^(2^k) mod n much more cheaply:
    g^(2^k mod phi(n)) mod n.

Just confirm that x and y work as claimed.

This is quite novel, and I'm not convinced yet that the AT requirement behaves
like I think it does. Maybe there's something terribly wrong with it. Tell me
if this is apparent. :)

yarrkov -- http://cipherdev.org/

More information about the cryptography mailing list