Towards Practical Data-Dependent Memory-Hard Functions with Optimal Sustained Space Trade-offs in the Parallel Random Oracle Model

arXiv:2508.06795 · cs.CR · Submitted 2026-08-18 · Read on arXiv

Jeremiah Blocki, Blake Holman

cs.CR

Submitted: 2026-08-18

Updated: 2026-08-19

Comments: Accepted at CRYPTO 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Robustness — 79× in this paper · explained in 5 episodes
• Trace — 46× in this paper · explained in 2 episodes
• Parallel Random Oracle Model — 20× in this paper
• Memory-Hard Functions — 19× in this paper
• Topological Order — 4× in this paper · explained in 2 episodes
• Amortization — 3× in this paper · explained in 1 episode
• Abstraction — 1× in this paper · explained in 1 episode
• Core — 1× in this paper · explained in 2 episodes
• Generalization — 1× in this paper · explained in 13 episodes

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs