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

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. (EURO-CRYPT 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 Ω(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 = Ω(N/ log N ) sustained complexity t = Ω(N ) i.e., any algorithm evaluating the function in the parallel random oracle model must have at least t = Ω(N ) steps where the memory usage is at least Ω(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 such as Argon2id and Scrypt. We design our own dynamic graph (dMHF) with the property that any dynamic pebbling strategy either (1) has Ω(N ) rounds with Ω(N ) space, or (2) has CMC Ω(N 3-)substantially larger than N 2 . For Argon2id we show that any dynamic pebbling strategy either(1) has Ω(N ) rounds with Ω(N 1-) space, or (2) has CMC ω(N 2 ). We also present a dynamic version of DRSample (Alwen et al. 2017) for which any dynamic pebbling strategy either (1) has Ω(N ) rounds with Ω(N/ log N ) space, or (2) has CMC Ω(N 3 / log N ).