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.
From: Blake Holman [view email]
[v1]
Sat, 9 Aug 2025 02:57:22 UTC (6,371 KB)
[v2]
Tue, 18 Aug 2026 17:46:59 UTC (346 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。