This says $f_n$ is memory hard if, for any space $S$ and time $T$, $S\cdot T \in \Omega(n^2)$.

My questions:

  • What is $S$? Space? E.g. bytes of available memory?
  • What is $n$? Bytes of requested memory by the memory hard function?
  • What is $T$? Number of rounds?
  • How good is this definition? E.g. how tight is it? E.g. $\Omega(n^2)$ is asymptotic lowest bound, but I guess not all functions that are $\in \Omega(n^2)$ are equal. E.g. perhaps some are better? So I guess this definition is not tight enough to show us which memory-hard KDF is necessarily better?
  • Any better memory-hardness definition? E.g. more tight than simply $\in \Omega(n^2)$?

Many of these are addressed in the article. In this setting, the "adversary" is some algorithm that can evaluate $f_n$ using less resources than we had hoped.

  • $S$ = space/memory usage of the adversary. In this line of work, $f_n$ is a function that makes calls to some random oracle $H : \{0,1\}^k \to \{0,1\}^k$, and we measure the (worst-case) space usage in the units of $k$-bit "blocks."

  • $T$ = time usage of the adversary. Usually measured in number of calls to $H$. In some models the adversary is allowed to make parallel calls to $H$ for free, so $T$ is the number of "sequential rounds" of calls to $H$.

  • $n$ = the tunable hardness parameter of the memory-hard function. Larger $n$ makes it more difficult to evaluate the function $f_n$ (and ideally the amount of "effort" is quadratic in $n$). Honest parties should choose the largest $n$ such that the they are willing to spend the effort to evaluate $f_n$.

How good is this definition? ... So I guess this definition is not tight enough to show us which memory-hard KDF is necessarily better?

It's true that $n^2/1000$ is a lot different than $1000n^2$, but this definition would be fine with both of them as measures of difficulty for $f_n$. At the time of this paper, most candidate memory-hard functions were asymptotically much worse than $\Theta(n^2)$. So this definition is quite effective to rule out many bad candidates. Once you have many candidates that satisfy this asymptotic definition, then you can start to worry about the constant factors.

Any better memory-hardness definition?

Yes, this definition only considers the worst case space usage $S$. Suppose $f_n$ is a function that indeed requires $n$ units of memory to evaluate -- there is no way to evaluate $f_n$ without holding $n$ units of memory at some point. This doesn't rule out the possibility that $n$ units of memory are required only for a very short window of time. In other words, there could be an algorithm for $f_n$ whose plot of memory usage over time looks like this:

enter image description here

(images taken from Leo Reyzin's slides on scrypt)

If this algorithm has maximum space usage $n$ and also uses $n$ time, its ST-complexity is $\Omega(n^2)$. ST-complexity is like the area of the blue rectangle in this picture.

But this measure of memory-hardness obscures some problem. If an adversary wants to evaluate $f_n$ on many different inputs, it can do so by cleverly scheduling things like this:

enter image description here

You can use this approach to evaluate this example $f_n$ on $n$ different inputs using only $O(n)$ time and $O(n)$ total memory! So the total "ST-cost" to evaluate the function $n$ times is $O(n^2)$, meaning that the amortized cost per instance is only $O(n)$.

A better way to classify the memory-hardness of a function would be to measure the "area under the curve" rather than the area of the "bounding box". This is indeed what is proposed in subsequent works, where the memory-hardness-metric is called "cumulative memory complexity."

  • $\begingroup$ nice answer, I learnt quite a bit from it. $\endgroup$
    – kodlu
    Sep 3 at 1:39
  • $\begingroup$ Yes, people forgot the amortized cost many times. And, this is why memory-hard functions need random access all the time. $\endgroup$
    – kelalaka
    14 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.