3
$\begingroup$

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)$?
$\endgroup$

1 Answer 1

5
$\begingroup$

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 complexity 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 $S$ is the (worst-case) space usage of the adversary, measured in $k$-bit "blocks."

  • $T$ = time complexity 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$ increases the effort required to evaluate the function $f_n$ (and ideally the effort scales quadratically 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 happy with memory-hard functions with either of these levels of difficulty. 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 bounding-box rectangle in this picture.

But this measure of memory-hardness obscures some problem. Suppose an adversary wants to evaluate $f_n$ on many different inputs, and it cleverly schedules those evaluations like this:

enter image description here

This strategy can be used to evaluate the 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."

$\endgroup$
2
  • $\begingroup$ nice answer, I learnt quite a bit from it. $\endgroup$
    – kodlu
    Commented Sep 3, 2021 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
    Commented Oct 16, 2021 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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