I found this term in Scrypt's paper. I have several questions about its meaning, ranging from how to parse it, to theoretical bounds:
Q1: How to parse it?
- Is it read
Q2: What does it mean?
- Does it mean that as space is linearly reduced, then penalty is that is exponentially increased?
- Can we tell what is that exponent? Or does suffice to simply be an exponent, regardless of which exponent?
- In current practice, can we say something more specific about what that exponent for state-of-art functions beyond just "it's exponential"? I think it is within reach to make more specific claims.
- Ideally, is there any theorem that shows an upper bound for this exponent? E.g. can we say, for every reduced single unit of memory, amount of computation performed doubles? Tripples? Quadruples? ...?
Q3: Any better name?
- Is the name used in Scrypt's paper still the most accurate name?
- Is there a better name for it that the cool kids like to use nowadays more? In Argon2's paper, as well as Here, it seems to be called
memory-hard. Does it mean that
memory-hardis the better name to adopt? E.g. what do the coolest gurus in top cryptographic journals tend to use?
- Optional: any reason the Scrypt paper didn't call it
memory-hard? Or was it just the randomness of life?
I did look at previous related answers, and I found these: