  Pebble games were originally formulated to study time-space tradeoffs in
computation, modeled by games played on directed acyclic graphs (DAGs). Close
connections between pebbling and cryptography have been known for decades. A
series of recent research starting with (Alwen and Serbinenko, STOC 2015) has
deepened our understanding of the notion of memory-hardness in cryptography ---
a useful property of hash functions for deterring large-scale password-cracking
attacks --- and has shown memory-hardness to have intricate connections with
the theory of graph pebbling.
  In this work, we improve upon two main limitations of existing models of
memory-hardness. First, existing measures of memory-hardness only account for
dynamic (i.e., runtime) memory usage, and do not consider static memory usage.
We propose a new definition of static-memory-hard function (SHF) which takes
into account static memory usage and allows the formalization of larger memory
requirements for efficient functions, than in the dynamic setting (where memory
usage is inherently bounded by runtime). We then give two SHF constructions
based on pebbling; to prove static-memory-hardness, we define a new pebble game
("black-magic pebble game"), and new graph constructions with optimal
complexity under our proposed measure.
  Secondly, existing memory-hardness models implicitly consider linear
tradeoffs between the costs of time and space. We propose a new model to
capture nonlinear time-space trade-offs and prove that nonlinear tradeoffs can
in fact cause adversaries to employ different strategies from linear tradeoffs.
  Finally, as an additional contribution of independent interest, we present
the first asymptotically tight graph construction that achieves the best
possible space complexity up to $\log{\log{n}}$-factors for an existing
memory-hardness measure called cumulative complexity in the sequential pebbling
model.
