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

Abstract

Memory-Hard Functions (MHFs) protect passwords and other low-entropy secrets against brute-force attacks. Sustained space complexity (SSC), the strongest natural formalization of memory hardness, measures how long an attacker's memory remains above a threshold. Since no function computable in sequential time $\Theta (N)$ can force every parallel attacker to sustain $\Theta (N)$ memory for $\Theta (N)$ steps, the appropriate goal is a strong tradeoff between SSC and cumulative memory complexity (CMC). Blocki and Holman (CRYPTO 2022) established such tradeoffs in the dynamic pebbling model, but their construction used 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 data-dependent MHF, DEGSample, and prove the first SSC/CMC tradeoff for data-dependent MHFs directly in the PROM. In the dynamic pebbling model, every strategy either sustains $\Omega (N)$ memory for $\Omega (N)$ steps or incurs the maximal CMC penalty $\Omega (N^{3-\epsilon })$. In the PROM, every attacker either sustains $\Omega (N)$ memory for $\Omega (N)$ steps or incurs CMC at least $\Omega (N^{2.5-\epsilon })$. We introduce ancestral robustness and show that, together with fractional depth-robustness, it yields strong PROM tradeoffs under a natural dynamization procedure. The lower bound combines a time-space tradeoff with an extraction procedure converting any PROM execution into a cost-equivalent pebbling of the realized graph.

Accepted at CRYPTO 2026