# Minimalist memory-hard function?

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

• Comments are not for extended discussion; this conversation has been moved to chat. Sep 7, 2016 at 12:16

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.

• I suggest that detailed critics to this design should be in a separate answer to the same question; If there happens to be another design, it will be possible to create a separate question criticizing this design, and move the corresponding answer to that.
– fgrieu
Sep 13, 2016 at 12:44
• re: the permutation: Over the course of one round, it appears that the least significant bits do not influence the most significant bits; Applying permutation(byte) on bytes in the range 0...255 produces output with the 16 most significant bits consistently set to 0. Perhaps you would like to verify my implementation functions correctly. I'm not sure if the permutation was supposed to be applied for multiple rounds. I haven't investigated the memory hard part yet. Sep 13, 2016 at 16:37