Static-Memory-Hard Functions and Nonlinear Space-Time Tradeoffs via Pebbling.

Pebble games were originally formulated to study time-space tradeoffs incomputation, modeled by games played on directed acyclic graphs (DAGs). Closeconnections between pebbling and cryptography have been known for decades. Aseries of recent research starting with (Alwen and Serbinenko, STOC 2015) hasdeepened our understanding of the notion of memory-hardness in cryptography ---a useful property of hash functions for deterring large-scale password-crackingattacks --- and has shown memory-hardness to have intricate connections withthe theory of graph pebbling.

In this work, we improve upon two main limitations of existing models ofmemory-hardness. First, existing measures of memory-hardness only account fordynamic (i.e., runtime) memory usage, and do not consider static memory usage.We propose a new definition of static-memory-hard function (SHF) which takesinto account static memory usage and allows the formalization of larger memoryrequirements for efficient functions, than in the dynamic setting (where memoryusage is inherently bounded by runtime). We then give two SHF constructionsbased on pebbling; to prove static-memory-hardness, we define a new pebble game("black-magic pebble game"), and new graph constructions with optimalcomplexity under our proposed measure.

Secondly, existing memory-hardness models implicitly consider lineartradeoffs between the costs of time and space. We propose a new model tocapture nonlinear time-space trade-offs and prove that nonlinear tradeoffs canin fact cause adversaries to employ different strategies from linear tradeoffs.

Finally, as an additional contribution of independent interest, we presentthe first asymptotically tight graph construction that achieves the bestpossible space complexity up to $\log{\log{n}}$-factors for an existingmemory-hardness measure called cumulative complexity.