# [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.

Challenge:
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

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

Verification:
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/

```