Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus making attacks on hashes less economical.
Background
I attended a seminar on recent publication, Scrypt is Maximally Memory-Hard 1, where the authors focus on scrypt, a simple candidate Memory-hard function (MHF) designed by Percival, and described in RFC 7914.
From the abstract:
We prove that scrypt is optimally memory hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is $\Omega(n^2 \cdot w)$, where $w$ and $n$ are the output length and number of invocations of the underlying hash function, respectively.
Additionally in the introduction:
In this work, in Section 5, we also prove an optimal $\Omega(n^2 \cdot w)$ lower bound on the parallel cumulative pebbling complexity for a game which abstracts the evaluation of scrypt: we consider a path of length $n$, and an adversary must pebble $n$ randomly chosen nodes on this graph, where the ith challenge node is only revealed once the node of challenge $i − 1$ is pebbled. This already gives an optimal $\Omega(n^2 \cdot w)$ lower bound on $cc_{mem}$ for scrypt for adversaries who are only allowed to store entire labels, but not any functions thereof.
From my understanding, it would be possible for an adversary to formulate a strategy that is a suitable compromise between memory and runtime complexity, e.g. where pebbles for $X_0, X_1, \dots , X_{n−1}$ are stored for only the even $i$, thus halving the worst case memory usage, while also having the worst case runtime, but yet leaving the total memory·time cost the same as before.
Question
For a single system, I'd say hardware cost is nonlinear with respect to CPU performance or size of onboard memory, i.e components representing the extreme of either spectrum may be exponentially more expensive. Thus to lessen the rate of return or increase the necessary capital investment an attacker would expect, we might like to mitigate the usability of midrange hardware that would otherwise be the most economical to use.
To visualize my rudimentary thoughts, I've included a crude graph below, where x and y axis are memory and time usage. The volume of the orange rectangle intersecting the purple line at the green point represents the total memory·time cost for any configuration, e.g. if you had sufficient memory one could compute the hash in $\frac{1}{2}$ time units. I was wondering if a problem could be formulated such make the memory·time cost follow the red curve instead, thus pushing an adversary further towards hardware extremes to achieve optimal memory·time costs while to the detriment of hardware cost.
Perhaps there are studies some of you may know that touch on optimal efficient outcomes from an economic standpoint, i.e. considering hardware investment, operational costs, expected return per solution. I guess this sounds like a miners optimization problem when working with crypto currencies that require proof of work, but I'm slightly more interested in the economics the motivate attackers or scammers.
@misc{cryptoeprint:2016:989,
author = {Jo\"el Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro},
title = {Scrypt is Maximally Memory-Hard},
howpublished = {Cryptology ePrint Archive, Report 2016/989},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/989}},
}
Basically
Are there any functions that render a linear combination of memory or runtime approaches less efficient than committing solely to either a memory or compute speed optimizations, thus always making midrange hardware unsuitable for profitable attacks?
