Why do memory-hard functions rely on a time-space trade-off?

$$S(n) \times T(n) \in \Omega(\mathrm{Poly}(n))$$

I understand memory-hard functions are trying to impose heavy memory usage to counter ASIC attacks. But I don't understand why heavy memory usage must be measured with a time-space trade-off.

There are problems proven to be memory-heavy (at least the most memory-heavy in its class). Search PSPACE and EXPSPACE will return a list of results.

Computational complexity tells us that if a problem requires a lot of memory to run, then it also requires a lot of time to run. Wouldn't these problems be better used as memory-hard functions than those with a time-space trade-off?

• Non-answer: A positive aspect of the trade off is that you can migrate a password encrypted drive to a computer with less RAM and still have the ability to decrypt it. Jul 13 '18 at 5:06

In order to create such a function you fill up memory with results of some computation; the memory-hard function then reads these values to further the computation later on.

Rather than saving the values, one could theoretically re-calculate them when needed. So the memory is not really a hard requirement. The memory hard functions are however build in such a way that they require much more computation without memorization of the intermediate values. This is the time / memory trade off.

• Professional answers deserve a professional review / formatting :) Jul 14 '18 at 11:22

It is true that many memory-hard functions (MHFs) only give a time-space tradeoff. Take the example of scrypt, which was proven to have optimal cumulative memory complexity $\Omega(n^2)$ in:

Joël Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro: Scrypt is Maximally Memory-Hard. Eurocrypt 2017

Cumulative memory complexity only counts the sum of memory usage over the length of the algorithm. It does not preclude an algorithm taking $O(n^2)$ time but only $O(1)$ space, and indeed it is not hard to see that scrypt does have such an algorithm. From what I understand, this is how it is implemented by most ASICs, so the "optimal memory hardness" (paradoxically) does not prevent folks from evaluating it using basically no memory.

This odd situation is what has inspired more fine-grained definitions of memory-hardness, for example sustained memory complexity:

Joel Alwen and Jeremiah Blocki and Krzysztof Pietrzak: Sustained Space Complexity. Eurocrypt 2018.

Sustained complexity allows you to say things like "to evaluate this function you must use $\Omega(n/\log n)$ amount of memory for $\Omega(n)$ steps." So this is a step in the direction that you suggest.

• The honest algorithm is a sequential algorithm that uses $n$ time and $n$ memory
• No parallel algorithm uses significantly less than $n$ time, $n$ space (and ideally requires both simultaneously)
So you have to find a way to rule out speedups from parallelization. And it's actually worse than that, since you also want to rule out speedups from amortization (solving $k$ instances with less $\alpha n$ time and $\beta n$ memory for $\alpha \beta < k$).