Data-Dependent Memory-Hard Functions: Sustained Space and Cumulative Complexity Trade-Offs in the Parallel Random Oracle Model

Memory-Hard Functions (MHFs) are a cryptographic primitive designed to protect passwords and other low-entropy secrets against brute-force attacks. The strongest and most natural formalization of memory-hardness is sustained space complexity (SSC), which measures how long an attacker's memory remains above a given threshold. Ideally, one would like to ensure that any parallel attacker must sustain Θ(N ) memory for Θ(N ) steps, while the function can also be computed in sequential time Θ(N ). Unfortunately, this goal is impossible to achieve. Thus, the appropriate objective is to establish strong tradeoffs between sustained space complexity and cumulative memory complexity (CMC), another strong notion of memory hardness. Blocki and Holman (CRYPTO 2022) achieved strong SSC/CMC tradeoffs in the dynamic pebbling model, but their construction relied on expensive combinatorial graphs, and the pebbling abstraction does not rule out more efficient attacks in the stronger Parallel Random Oracle Model (PROM). We address both limitations. We construct a new data-dependent MHF (dMHF), DEGSample, and prove the first SSC/CMC tradeoff for dMHFs directly in the PROM. In the dynamic pebbling model, DEGSample achieves the same ideal tradeoff as prior work: any dynamic pebbling strategy either sustains Ω(N ) memory for Ω(N ) steps or incurs a maximal CMC penalty Ω(N 3-ϵ ). In the PROM, we prove that any attacker either sustains Ω(N ) memory for Ω(N ) steps or incurs a steep CMC penalty of at least Ω(N 2.5-ϵ ). To prove this, we introduce a new graph property called ancestral robustness and show that, together with another property called fractional depth-robustness, it suffices to obtain strong PROM tradeoffs via a natural dynamization procedure to turn the graph into a dMHF. The PROM lower bound combines a timespace trade-off argument with an extraction procedure that converts any PROM execution into a cost-equivalent pebbling of the realized graph.