Minimalist memory-hard function?

Question

What would be a minimalist memory-hard function, reasonably conjecturable to

• require $\approx2^k$ bits of memory per running evaluation, $k\approx32$;
• require $\approx2^n$ R/W accesses to $2^w$-bit words per evaluation, $w\approx6$ (likely $n\ge k-w+3$ or something on that tune);
• be practically impossible to significantly optimize using a much smaller cache memory or a different word width so as to lower the above number of accesses?

My purpose is convincing a hardware designer that speeding-up a full-blown memory-hard function, much beyond the cost of main memory accesses, is doomed; see comments there. I thus don't care about proof of the conjectures, that auxiliary functions (as used for computing addresses and data) offer more than basic cryptographic strength, resistance to hypothetical optimizations requiring at least twice as much more main memory, side-channel resistance..

Answer 1

Tentative answer to my own question. Please criticize!

All variables in capital are one 128-bit word, with $w=7$. Parameters are as in the question, and $k-4\le n\le128$. I use an auxiliary arbitrary public permutation $\large\mathscr P$ of one word; a simplistic one is constructed using Addition-Rotation-Xor. A function evaluation goes:

• set $D$ to the function's input
• memory setup: repeat for $C$ from $2^{k-w}-1$ down to $0$
  • write $D$ to memory at address $C$
• set $A$ to zero.
• main loop: repeat for $C$ from $2^n-1$ down to $0$
  1. set $A$ to $A\oplus{\large\mathscr P}(D\oplus C)$
  2. read $R$ from memory at address $A\bmod2^{k-w}$
  3. write $D$ to memory at same address
  4. set $D$ to $D\oplus{\large\mathscr P}(R\oplus C)$
• output $D$.

Some rationale of the design:

• Address of the next memory location used depends, thru two nested invocations $\large\mathscr P$ and depending on chronology thanks to $C$, on the value previously read $R$, and will-be result $D$.
• The main loop has reversible effect on the combination of memory, $A$ and $D$; hence the input-to-output entropy loss can be estimated as at most 0.8272… bits.
• Mixing of counter $C$ makes getting into a short cycle unconceivable.
• The average number of accesses to each memory cell is at least 8.

---

Permutation $\large\mathscr P$ is:

• set $X$ to the function's input
• repeat for $t$ each of the six constants 3, 5, 7, 13, 23, 43
  • set $X$ to $3\big(X\oplus(X\operatorname{\lll}t)\big)\bmod2^{128}$ where $\lll$ is left rotation on 128 bits
• output $X$.

Note following comment: this is a toy/simplistic permutation, not to be reused outside the present context of deep iteration, and was not the focus of the answer. There are far less rounds than necessary for complete propagation of a bit difference; but in the context, two invocations (thus twice more rounds) are nested from $R$ to $A$. Zero is a stationary point, since the only constants are rotation counts (hastily obtained by starting from 3, doubling, and rounding down to the next prime).
Tentative test vector: for ${\large\mathscr P}\big({\large\mathscr P}(1)\big)$ I get 0x5be8f27af383369a91de3e614e6650dd.