Paper 2022/832

Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions

Blake Holman, Purdue University West Lafayette

Abstract

Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product of running time and the maximum space usage over the entire execution of an algorithm. Alwen and Serbinenko (STOC 2015) observed that the space-time cost of evaluating a function multiple times may not scale linearly in the number of instances being evaluated and introduced the stricter requirement that a memory-hard function has high cumulative memory complexity (CMC) to ensure that an attacker's amortized space-time costs remain large even if the attacker evaluates the function on multiple different inputs in parallel. Alwen et al. (EUROCRYPT 2018) observed that the notion of CMC still gives the attacker undesirable flexibility in selecting space-time tradeoffs e.g., while the MHF Scrypt has maximal CMC $\Omega(N^2)$, an attacker could evaluate the function with constant $O(1)$ memory in time $O(N^2)$. Alwen et al. introduced an even stricter notion of Sustained Space complexity and designed an MHF which has $s=\Omega(N/\log N)$ sustained complexity $t=\Omega(N)$ i.e., any algorithm evaluating the function in the parallel random oracle model must have at least $t=\Omega(N)$ steps where the memory usage is at least $\Omega(N/\log N)$. In this work, we use dynamic pebbling games and dynamic graphs to explore tradeoffs between sustained space complexity and cumulative memory complexity for data-dependent memory-hard functions. We design our own dynamic graph (dMHF) with the property that {\em any} dynamic pebbling strategy either (1) has $\Omega(N)$ rounds with $\Omega(N)$ space, or (2) has CMC $\Omega(N^{3-\epsilon})$ --- substantially larger than $N^2$. We also present a dynamic version of DRSample (Alwen et al. 2017) for which {\em any} dynamic pebbling strategy either (1) has $\Omega(N)$ rounds with $\Omega(N/\log N)$ space, or (2) has CMC $\Omega(N^3/\log N)$.

Note: The original paper contained a flawed proof claiming that any dynamic pebbling strategy for Argon2id either (1) requires Ω(N) rounds with Ω(N^{1−ε}) space, or (2) has cumulative memory complexity ω(N²). Specifically, the proof of Lemma 16 is incorrect, and the proofs of Theorem 8 and Corollary 3 rely on Lemma 16 and are therefore also flawed. Accordingly, we have removed this claim from the abstract. We conjecture that the claim remains true, but leave this as an open question.

@misc{cryptoeprint:2022/832,
      author = {Jeremiah Blocki and Blake Holman},
      title = {Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/832},
      year = {2022},
      url = {https://eprint.iacr.org/2022/832}
}