Using k-SUM to Create an ASIC/FPGA Resistant PoW

[tromp]

and assume d = O(n^3).

I'm using the assumption that d == n.

That's no good. If you aim to use 1Gbit of memory (128MB), and
set d = n = 2^30, then there are about (n choose 3)/d ~ 2^60/6
solutions, taking forever to try all, and you're not progress-free.

Like I said before, you need to choose d and n so that you expect at
most one solution.

[optimiz3]

Like I said before, you need to choose d and n so that you expect at
most one solution.

I suppose so - working through all this it seems we've established kSUM is equivalent to the Birthday Problem but with k collisions instead of two.

[tromp]

Then 3-SUM can be solved in O(n) memory and O(n^2) time, by storing all h_i
as keys in a set S, and running

for i = 1 to n
   for j =i+1 to n
      if S contains -(h_i + h_j) mod d
        then 3-SUM found

You've got another problem here in that it is trivial to trade-off memory for time
(e.g. do the above twice, first for half of S that is even, then for the other half that's odd).

So 2-SUM and 3-SUM both seem to be memory-easy rather than memory-hard.

4-SUM and higher don't seem immune to such trade-offs either.

[optimiz3]

Yes - agreed.  Better to establish equivalence to an existing problem now than later.  Appreciate the feedback and glad this structure was explored more thoroughly.