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
some other tradeoff.
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/
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
