Memory-Hard Functions from Cryptographic Primitives

Abstract

Memory-hard functions (MHFs) are moderately-hard functions which enforce evaluation costs both in terms of time and memory (often, in form of a trade-off). They are used e.g. for password protection, password-based key-derivation, and within cryptocurrencies, and have received a considerable amount of theoretical scrutiny over the last few years. However, analyses see MHFs as modes of operation of some underlying hash function $\mathcal {H}$, modeled as a monolithic random oracle. This is however a very strong assumption, as such hash functions are built from much simpler primitives, following somewhat ad-hoc design paradigms.

This paper initiates the study of how to securely instantiate $\mathcal {H}$ within MHF designs using common cryptographic primitives like block ciphers, compression functions, and permutations. Security here will be in a model in which the adversary has parallel access to an idealized version of the underlying primitive. We will provide provably memory-hard constructions from all the aforementioned primitives. Our results are generic, in that we will rely on hard-to-pebble graphs designed in prior works to obtain our constructions.

One particular challenge we encounter is that $\mathcal {H}$ is usually required to have large outputs (to increase memory hardness without changing the description size of MHFs), whereas the underlying primitives generally have small output sizes.

1 Introduction

Memory-hard functions (MHFs) are functions which are moderately hard to compute both in terms of time and memory, in the sense that their computation is subject to a time-memory trade-off – relatively fast computation requires memory, whereas low-memory implies slow (or even very slow) computation. This ensures for example that the area-time complexity of custom-made hardware (e.g., ASICs) needed to evaluate MHFs is large (and thus, the dollar cost of this hardware), and this fact makes them suitable for password hashing, password-based key derivation, and proof of work in cryptocurrencies, where attackers may leverage such hardware. The first practical MHF, Scrypt, was proposed by Percival [19, 20]. Starting with Alwen and Serbinenko [7], several works have been devoted to the theoretical analysis of MHFs (cf. e.g. [1,2,3,4,5,6,7,8, 12,13,14]), also exposing weaknesses in practical designs like Argon2 [10] (the winner of the password-hashing competition), Catena [17], and Balloon hashing [13].

The starting point of our work is the observation that theoretical works describe MHFs as modes of operation of an underlying primitive, usually a (hash) function $\mathcal {H}: {\{0,1\}} ^{M} \rightarrow {\{0,1\}} ^{{W}}$ (where $M \ge {W}$), modeled as a random oracle [9] within security proofs. However, this completely ignores the implementation details behind $\mathcal {H}$ which may make it far from an ideal random oracle – often, such designs are completely ad-hoc and based on much simpler objects (e.g., Scrypt’s resembles a permutation-based stream-cipher design), in particular because ${W}$ is much larger than for conventional hash functions (e.g., a few thousand bits).

Therefore, we would like to study MHFs at a finer level of granularity that considers the inner structure of $\mathcal {H}$, and we would like to understand how such an $\mathcal {H}$ is meant to be built in a sound way. We stress that it is not enough for $\mathcal {H}$ to be a random oracle in the sense of indifferentiability [18], since memory-hardness definitions are multi-stage games to which indifferentiability does not apply [22]. Therefore, such analyses would call for completely new theory.

We also note that the primitive on which an MHF is based matters – Ren and Devadas [21] pointed out the advantages of building MHFs from AES, as the availability of on-chip hardware implementations (AES-NI) significantly reduces the efficiency speed-up of dedicated hardware by ensuring a conventional CPU can evaluate the function already at a cost similar to that of dedicated hardware.

This paper initiates the study of provably-secure MHFs built from basic symmetric primitives, which we model as ideal – we consider block ciphers, permutations and compression functions. We prove general results that will enable us to obtain MHFs based on them, in a model where these primitives are ideal and the adversary is allowed to make multiple calls in parallel. (This naturally adapts the parallel random-oracle model from previous MHF analyses to primitives.)

As our first contribution, we provide one-call efficient instantiations of $\mathcal {H}$ from such primitives. We will adapt previous lemmas based on “ex-post-facto arguments” (dating back to [15]) to reduce the security of a large class of MHFs based on directed acyclic graphs (DAGs) to the pebbling complexity of the underlying DAG. (These are usually called data-independent MHFs, or iMHFs for short, and are favored designs due to their resilience to side-channel attacks.)

This will already give us iMHFs from all aforementioned primitives. However, a DAG ${\mathbb {G}}$ of N vertice yields a function whose computation operates on N memory blocks of size L bits, where L is the output length of the primitive (e.g., $L = 128$ bits for AES). In this case, a good choice of ${\mathbb {G}}$ would ensure that product of time and memory¹ to evaluate the function is (nearly) $\varOmega (N^2 L)$ – increasing memory hardness means increasing N, which leads to a larger function description. A better option (consistent with practice) is to keep the same graph, but operate on larger blocks of size ${W} \gg L$, to ensure the time-memory product is now $\varOmega (N^2 W)$.

To do this, we will provide a generic construction of an $\mathcal {H}$ with ${W}$-bit output using an underlying primitive with a shorter output. We will refer to $\mathcal {H}$ as a wide-block labeling function (as opposed to a small-block one like those we gave above), and the resulting MHF will be called a wide-block MHF. (Our design will have the added benefit of allowing for a variable ${W}$.) Our construction will guarantee the final MHF is memory hard as long as the graph ${\mathbb {G}}$ is sufficiently depth-robust, a notion we review below.

We stress that all practical constructions implicitly design wide-block labeling functions, for which existing analyses provide no guarantees, as they abstract them away as random oracles, which they are not. While we failed to provide either proofs or attacks on practical designs, initiating the study of provably secure constructions in the more realistic primitive-based setting is an important step.

The remainder of this section will provide a more in-detail overview of our results, as well as a concise introduction to the formalism.

1.1 Overview of Our Results

Before highlighting our result in more detail, we briefly review some notions at an informal level.

This paper deals with graph-based data-independent MHFs (which we refer to as iMHFs, for short), defined by a DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ on ${N}$ vertices. For simplicity, we assume ${\mathbb {V}} = \{v_1, \ldots , v_{{N}}\}$, and each edge has the form $(v_i, v_j)$ where $i < j$, i.e., vertices are topologically order – vertex $v_1$ is the source, $v_{{N}}$ is the (unique) sink. Previous works [3, 7] use ${\mathbb {G}}$ and a labeling function $\mathcal {H}: {\{0,1\}} ^{\le {\delta } {W} +\log {N}} \rightarrow {\{0,1\}} ^{{W}}$ (we refer to ${W}$ as the block length of the MHF and ${\delta }$ the maximal indegree of ${\mathbb {G}}$) to instantiate an MHF $\mathcal {F}_{{\mathbb {G}}, \mathcal {H}}$. On input M, we first assign the label $\ell _1 = \mathcal {H}(\langle 1\rangle \Vert M)$ to the source, where $\langle i \rangle$ is a $O({\text {log}} N)$-bit encoding of i, and then each vertex $v_i$ is assigned a label

$$\begin{aligned} \ell _i = \mathcal {H}(\langle i \rangle \Vert \ell _{j_1} \Vert \ldots \Vert \ell _{j_d}) \;, \end{aligned}$$

where $v_{j_1}, \ldots ,v_{j_d}$ are the predecessor vertices of $v_i$. Finally, we output $\ell _{{N}}$.

To capture the evaluation costs for $\mathcal {F}_{{\mathbb {G}}, \mathcal {H}}$, following [7] we adopt the cumulative memory complexity (CMC). We model the labeling function $\mathcal {H}$ as a random oracle, and assume the adversary proceeds in steps. In each step i, the adversary holds state $\sigma _{i-1}$ (where $\sigma _0 = M$), and can compute a vector of queries to $\mathcal {H}$, as well as next state $\sigma _i$, which it will receive in the next step, together with the outputs of the evaluations of $\mathcal {H}$ on the query vector. The CMC of the adversary is defined as the sum of the sizes of states, and ${{\mathsf {CMC}}} (\mathcal {F}_{G, \mathcal {H}})$ denotes the best-possible (expected) CMC of an adversary to evaluate $\mathcal {F}_{G, \mathcal {H}}$.

The evaluation of $\mathcal {F}_{{\mathbb {G}}, \mathcal {H}}$ is tightly related to a (parallel) pebbling game for the graph ${\mathbb {G}}$. Initially, the graph has no pebble on it, but in each step ${i}$, the player can (i) remove any subset of the pebbles, and (ii) put a pebble on a vertex $v\in {\mathbb {V}}$ if all parents of v have been pebbled at the previous step. (This is vacuously true for the source.) Multiple legal moves can be taken in one single step. (This differs from traditional black pebbling games, where each step allows one single legal move.) The player wins the game if the sink node has been pebbled. The cumulative complexity (CC) of the pebbling is defined as the cumulative sum of the number of pebbles on the graph in each step, and the CC of the graph ${\mathsf {cc}} ({\mathbb {G}})$ is the minimal CC over all pebbling strategies.

Intuitively, a pebbling strategy is equivalent to an evaluation strategy for $\mathcal {F}_{{\mathbb {G}}, \mathcal {H}}$ which only remembers labels in its memory. In [7] it was shown that such strategies are essentially optimal, i.e., ${{\mathsf {CMC}}} (\mathcal {F}_{{\mathbb {G}}, \mathcal {H}}) \approx {\mathsf {cc}} ({\mathbb {G}}) \cdot {W}$.

Depth-robust graphs are class of graphs with high CC: Specifically, we say a graph ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ is $({e},{d})$-depth-robust if, after removing any nodes set $S \subseteq {\mathbb {V}}$ where $|S|\le {e}$, the subgraph ${\mathbb {G}}-S$ still has a path with length ${d}$. Previous work [3] proved that any $({e},{d})$-depth-robust graph ${\mathbb {G}}$ has cumulative complexity ${\mathsf {cc}} ({\mathbb {G}})\ge {e} \cdot {d}$. Also, they show that constructions of (constant indegree) depth-robust graphs with $de = \varOmega (N^2/{\text {log}}(N))$ exist, which gives best-possible CC [1]. Later on, Alwen, Blocki, and Harsha [2] gave a procedure that samples with high probability a graph with the same depth-robustness guarantees, with a much simpler description.

Our two main contributions provide generic methods to devise constructions of MHFs from a simple primitive, like a block cipher, a permutation (that can be instantiated from a fixed-key block cipher), or a compression function. We consider a natural extension of the above model where the adversary queries an ideal version of the primitive.

• 1. We first define a simple class of so-called small-block labeling functions ${{{\mathcal {H}}} _{\mathsf {fix}}}$ which make one call to an underlying primitive. They transform a hard-to-pebble graph ${\mathbb {G}}$ (with maximal indegree 2) into a memory hard function ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{\mathsf {fix}}}}}$ as described above, but where $\mathcal {H}$ is now instantiated from the underlying primitive via ${{{\mathcal {H}}} _{\mathsf {fix}}}$, and the resulting block length is ${L}$, the output length of the primitive. (E.g., if we used AES, then ${L} = 128$ bits.) Moreover, we prove that the CMC of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{\mathsf {fix}}}}}$ is approximately ${\mathsf {cc}} ({\mathbb {G}})\cdot {L}$.

• 2. We then consider the problem of extending the block length of an iMHF to increase memory hardness without changing the underlying graph ${\mathbb {G}}$. To this end, from ${{{\mathcal {H}}} _{\mathsf {fix}}}$ with output length ${L}$, we define and construct a class of wide-block labeling functions, which in fact support variable block length. For any tunable parameters ${\delta },{W} =2^{{w}}\in {\mathbb {N}}$, the wide-block hash function ${{{\mathcal {H}}} _{{\delta }, {w}}}:{\{0,1\}} ^{{\delta } {W}}\rightarrow {\{0,1\}} ^{{W}}$ turns any depth-robust graph ${\mathbb {G}}$ (with maximal indegree ${\delta }$) into a memory hard function ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ via graph labeling. The CMC of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ is approximately

  $${{\mathsf {CMC}}} ({{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}) \approx {\mathsf {cc}} ({\mathbb {G}})\cdot {\delta } {W} ^{3}/ {L} ^{2}\;.$$

  Note that this is larger than ${\mathsf {cc}} ({\mathbb {G}}) \cdot W$ because, intuitively, we need to make multiple calls to the primitive to evaluate H, and use extra memory. In particular, we prove that the evaluation of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ can be done sequentially with time $N \delta (W/L)^2$ and memory $N \cdot W$, i.e., the resulting CMC is $N^2 \delta W^3/L^2$, via a naive strategy which runs N times the best-possible algorithm to evaluate $\mathcal {H}$, and keeps all W-bit labels in memory, in addition to internal states. Hence, if ${\mathsf {cc}} ({\mathbb {G}}) = \varTheta (N^2/{\text {log}} N)$ and $\delta = O(1)$, this means that the best possible CMC can have a gain of a factor at most $O({\text {log}} N)$ over the “naive” sequential strategy. This is the same upper bound on the speed-up we could establish for iMHFs from monolithic random oracles.²

We stress that because these results are generic, constructions can be obtained by using any graph ${\mathbb {G}}$ (or distribution over graphs) with sufficient depth-robustness guarantees.³ We give some more details about these results next.

The small-block labeling functions ${{{\mathcal {H}}} _{\mathsf {fix}}}$ takes an input⁴ ${x} \in {\{0,1\}} ^{{L}}\cup {\{0,1\}} ^{2{L}}$ and outputs an ${L}$-bit label. For a compression function ${{\mathsf {cf}}}$, the resulting output is ${{\mathsf {cf}}} (x)$; for an ideal cipher ${{\mathsf {ic}}}$, we split the input into a key part ${k} \in {\{0,1\}} ^{{L}}\cup \{\bot \}$ (where $\bot$ is a designated key separate from the ${L}$-bit strings, which as with compression functions, will be necessary to implement variable input length) and an input part ${x} \in {\{0,1\}} ^{{L}}$, the resulting output is ${{\mathsf {ic}}} ({k},{x})\oplus {x}$; for a random permutation ${{\mathsf {rp}}}$, we denote as ${x} ^{*}$ the exclusive-or sum of ${L}$-bit input blocks and the output is ${{\mathsf {rp}}} ({x} ^{*})\oplus {x} ^{*}$.

For any graph ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$, the memory hardness of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{\mathsf {fix}}}}}$ is argued similarly as in previous work [7]. The high level idea is to transform the execution of any algorithm ${{\mathsf {A}}}$ that computes the MHF into an ex-post-facto pebbling for the graph ${\mathbb {G}}$, and argue that the cumulative memory complexity of ${{\mathsf {A}}}$ is proportional to the cumulative complexity of the pebbling. Here we generalize the technique of [7] – which relies on a compression argument – so that it works even if:

• 1. The ideal-primitive input contains no explicit information of the node v. (This was not the case in prior work.)

• 2. The adversary can make inverse queries to the ideal primitive (as we also consider block ciphers now).

• 3. The input length of the primitive is fixed, and usually shorter than the actual input length of the labeling function.

Remark 1

Note that Blocki et al. [11] independently proposed a proof that addressed the first and the third challenge. But to the best of our knowledge, our technique is the only one that works even if the adversary makes inverse queries.

Given a small-block labeling function ${{{\mathcal {H}}} _{\mathsf {fix}}}$ and tunable parameters ${\delta },{W} =2^{{w}}\in {\mathbb {N}}$, the wide-block labeling function ${{{\mathcal {H}}} _{{\delta }, {w}}}:{\{0,1\}} ^{{\delta } {W}}\rightarrow {\{0,1\}} ^{{W}}$ is essentially a graph labeling function built upon ${{{\mathcal {H}}} _{\mathsf {fix}}}$ and a gadget graph ${{\mathbb {G}} _{{\delta },{W}}}$. ${{\mathbb {G}} _{{\delta },{W}}}$ is the composition of two subgraphs, namely, a MIX graph ${\mathbb {G}} _{{\mathsf {mix}}}$, and a source-to-sink depth robust graph ${\mathbb {G}} _{{\mathsf {ssdr}}}=({\mathbb {V}} ^{'},{\mathbb {E}} ^{'})$ that satisfies for any subset $S\subseteq {\mathbb {V}} ^{'}$ (with bounded size), ${\mathbb {G}} _{{\mathsf {ssdr}}}-S$ has a long path starting from a source node of ${\mathbb {G}} _{{\mathsf {ssdr}}}$ and ending at a sink node of ${\mathbb {G}} _{{\mathsf {ssdr}}}$.

For any $({e},{d})$-depth-robust graph ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$, the CMC of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ is argued by opening the graph structure underlying ${{{\mathcal {H}}} _{{\delta }, {w}}}$, and consider ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ as a graph function built upon ${{{\mathcal {H}}} _{\mathsf {fix}}}$ and a bootstrapped graph ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$. We show that the graph ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$ is extremely depth-robust and thus has pebbling complexity $\varOmega ({\delta } {W} ^{3}/{L} ^{3})\cdot {e} {d}$. Then by the property of ${{{\mathcal {H}}} _{\mathsf {fix}}}$, we can build the connection between the CMC of ${{\mathcal {F}} _{{\mathbb {G}},{{{\mathcal {H}}} _{{\delta }, {w}}}}}$ and the CC of ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$.

Given any (bounded-size) nodes subset S of ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$, we show the existence of an extremely long path in ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}-S$ in three steps: First, S is transformed into a small set $S^{'}$ in ${\mathbb {G}}$, and we obtain a long path ${P}$ in ${\mathbb {G}}-S^{'}$ by depth-robustness of ${\mathbb {G}}$; second, by source-to-sink depth-robustness of the SSDR graph, each vertex v in ${P}$ is transformed into a path ${P^{*}_{v}}$ in ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}-S$; finally, the structure of the MIX graph helps to elegantly connect the paths in $\{{P^{*}_{v}} \}_{v\in {P}}$ into an extremely long path in ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}-S$.

Remark 2

Note that our wide-block labeling functions can only turn depth-robust graphs (instead of arbitrary graphs with high CC) into memory hard functions. It is hard to link CMC and ${\mathsf {cc}} ({\mathbb {G}})$ directly using our extension framework. The hardness lies in linking ${\mathsf {cc}} ({\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})})$ and ${\mathsf {cc}} ({\mathbb {G}})$. In particular, even if the gadget graph ${{\mathbb {G}} _{{\delta },{W}}}$ has high CC, we do not know how to prove that ${\mathsf {cc}} ({\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}) \ge {\mathsf {cc}} ({\mathbb {G}})\cdot {\mathsf {cc}} ({{\mathbb {G}} _{{\delta },{W}}})$. This is because we do not know how to transform a pebbling ${\mathsf {P}} _{1}$ (of ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$) into a legal pebbling ${\mathsf {P}} _{2}$ (of ${\mathbb {G}}$), and argue that ${\mathsf {cc}} ({\mathsf {P}} _{1})$ is at least ${\mathsf {cc}} ({\mathsf {P}} _{2})$ times ${\mathsf {cc}} ({{\mathbb {G}} _{{\delta },{W}}})$.

2 Preliminaries

Let ${\mathbb {N}}$ and ${\mathbb {R}}$ denote the sets of natural numbers and real numbers respectively. Denote by [n] the set of integers ${\left\{ 1, \dots , n\right\} }$. By $\log (\cdot )$ we always refer to binary logarithm. For strings x and y, |x| is the length of x and we use $x\Vert y$ or (x, y) to denote the concatenation of x and y. For a set ${\mathbb {X}}$, is the process of assigning to x an element picked uniformly from ${\mathbb {X}}$, and $|{\mathbb {X}} |$ denotes the number of elements in ${\mathbb {X}}$. For a distribution ${\mathcal {D}}$, we use $x \leftarrow {\mathcal {D}}$ to denote the sampling of x from distribution ${\mathcal {D}}$. For an algorithm ${{\mathsf {A}}}$, we use ${{\mathsf {A}}} (x; r)$ to denote the output of the algorithm on input x and random coins r.

2.1 Memory-Hard Functions in the Parallel Ideal Primitive Model

In this paper, we consider three ideal primitives, namely, compression functions, ideal ciphers, and random permutations. All primitives will have an understood block length ${L} = 2^{{\ell }}$, which is assumed to be a power of two. In the following context, we will omit ${L}$ in the ideal-primitive notation if there is no ambiguity.

Denote by ${{\mathbb {CF}}}$ the set of functions⁵ with domain ${\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}$ and image ${\{0,1\}} ^{{L}}$. Denote by ${{\mathbb {IC}}}$ the set of keyed permutations with domain ${\mathcal {K}} \times {\{0,1\}} ^{{L}}$ and image ${\{0,1\}} ^{{L}}$. For simplicity, the key space is set as ${\mathcal {K}} \,{:=}\,\{{\bot } \}\cup {\{0,1\}} ^{{L}}$ in the following context. Finally, we let ${{\mathbb {RP}}}$ be the set of permutations with input/output length ${L}$.

Towards modeling the computation of memory-hard functions, we generalize the Parallel Random Oracle Model defined by Alwen and Serbinenko [7] to Parallel Ideal Primitive Model. Let ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ be a type of ideal primitive set. For any oracle-aided algorithm ${{\mathsf {A}}}$, input ${x}$ and internal randomness ${r}$, the execution ${{\mathsf {A}}} ({x}; {r})$ works as follows. First, a function ${{\mathsf {ip}}}$ (with block length ${L}$) is uniformly chosen from the set ${{\mathbb {IP}}}$. The oracle-aided algorithm ${{\mathsf {A}}}$ can make oracle query to ${{\mathsf {ip}}}$ as follows: If ${{\mathsf {ip}}} ={{\mathsf {cf}}}$ is a randomly sampled compression function, the algorithm can make queries with form and receive value ${{\mathsf {cf}}} (x)$. If ${{\mathsf {ip}}} ={{\mathsf {ic}}}$ is a randomly sampled ideal cipher, the algorithm can make forward queries with form $(\text {``}{{\mathbb {IC}}} \text {''},+, k, x)$ and receive value ${{\mathsf {ic}}} (k,x)$, or make inverse queries with form $(\text {``}{{\mathbb {IC}}} \text {''},-, k, y)$ and receive value ${{\mathsf {ic}}} ^{-1}(k, y)$. Similarly, if ${{\mathsf {ip}}} ={{\mathsf {rp}}}$ is a randomly sampled permutation, the algorithm can make forward queries with form $(\text {``}{{\mathbb {RP}}} \text {''}, +, x)$ and receive value ${{\mathsf {rp}}} (x)$, or make inverse queries with form $(\text {``}{{\mathbb {RP}}} \text {''}, -, y)$ and receive value ${{\mathsf {rp}}} ^{-1}(y)$.

Let ${\sigma } _0 = ({x}, \emptyset )$ denote the initial input state. For each round $i\in {\mathbb {N}}$, ${{\mathsf {A}}} ({x}; {r})$ takes input state ${\sigma } _{i-1}$, performs unbounded computation, and generates an output state ${\bar{\sigma }} _{i} = ({\delta } _{i}, {\mathbf {q}} _{i}, {\mathbf {out}} _{i})$, where ${\delta } _{i}$ is a binary string, ${\mathbf {q}} _{i}$ is a vector of queries to the ideal primitive ${{\mathsf {ip}}}$, and each element of ${\mathbf {out}} _{i}$ is with form $(v,\ell _{v})$ where v and $\ell _{v}$ are ${L}$-bit output labels. We define ${\sigma } _{i}=({\delta } _{i}, {\mathbf {ans}} ({\mathbf {q}} _{i}))$ to be the input state for round $i+1$, where ${\mathbf {ans}} ({\mathbf {q}} _{i})$ is the vector of ideal primitive answers to ${\mathbf {q}} _{i}$. The execution terminates after round ${T} \in {\mathbb {N}}$ if $|{\mathbf {q}} _{{T}}|=0$. We use ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r})$ to indicate both the execution output (i.e., the concatenation of output labels) and the execution trace (i.e., all of the input and output states $({\sigma } _0, {\bar{\sigma }} _1, {\sigma } _1, \dots )$). We also assume an upper bound ${{\mathsf {q}}}$ on the total number of output labels/ideal primitive queries that an algorithm makes, i.e., $\sum _{i \ge 1} |{\mathbf {q}} _{i}|+ |{\mathbf {out}} _{i}|\le {{\mathsf {q}}}$. We call ${{\mathsf {A}}}$ a sequential algorithm if $|{\mathbf {q}} _{i}|=1$ for every $1\le i<{T}$, otherwise ${{\mathsf {A}}}$ is a parallel algorithm.

Given the trace ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r})$ on input ${x}$, randomness ${r}$ and ideal primitive ${{\mathsf {ip}}}$, we define as time complexity ${{\mathsf {Tm}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r}))$ the number of rounds ran by ${{\mathsf {A}}}$, and space complexity ${{\mathsf {Spc}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r}))$ the size of the maximal input state. Moreover, we define ${{\mathsf {Tm}}} ({{\mathsf {A}}})$ (and ${{\mathsf {Spc}}} ({{\mathsf {A}}})$) to be the maximal time (and space) complexity of ${{\mathsf {A}}}$ over all choices of ${x}$, ${r}$ and ${{\mathsf {ip}}}$.⁶ We define cumulative memory complexity (CMC) [7] in the parallel ideal primitive model.

Definition 1

(Cumulative Memory Complexity). Given trace ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r})$ (with input states $({\sigma } _0, {\sigma } _1, \dots )$). we define cumulative memory complexity

$$ {{\mathsf {CMC}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r})) \,{:=}\, \sum _{i= 0}^{{{\mathsf {Tm}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({x}; {r}))} |{\sigma } _i| $$

to be the sum of input states’ size over time. For a real value ${\epsilon } \in [0,1]$, and a family of functions ${{\mathcal {F}}} = {\left\{ {f} ^{{{\mathsf {ip}}}} : {\mathcal {X}} \rightarrow {\mathcal {Y}} \right\} } _{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$, we define the ${\epsilon }$-cumulative memory complexity of ${{\mathcal {F}}}$ to be

where the expectation is taken over the uniform choices of ${{\mathsf {ip}}}$ and ${r}$. ${{\mathcal {A}}} _{{x}, {\epsilon }}$ is the set of parallel algorithms⁷ that satisfy the following: with probability at least ${\epsilon }$ (over the uniform choices of ${{\mathsf {ip}}}$ and ${r}$), the algorithm on input ${x}$ and oracle ${{\mathsf {ip}}}$ outputs ${f} ^{{{\mathsf {ip}}}}(x)$.

We now define memory hard functions in the parallel ideal primitive model. Intuitively, there exists a relatively efficient sequential algorithm that computes the MHFs, and any parallel algorithm that evaluates the functions incurs high CMC cost.

Definition 2

(Memory Hard Functions). For an ideal primitive set ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$, a family of functions ${{\mathcal {F}}} = {\left\{ {f} ^{{{\mathsf {ip}}}} : {\mathcal {X}} \rightarrow {\mathcal {Y}} \right\} } _{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$ is $({\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}},{\varDelta _{{{\mathcal {F}}}}},T_{{{\mathcal {F}}}})$-memory hard if and only if the following properties hold. (${\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}},{\varDelta _{{{\mathcal {F}}}}}$ are functions that take as input a real value in (0, 1] and output a real value, $T_{{{\mathcal {F}}}}$ is an integer.)

• Memory-hardness: For any ${\epsilon } \in (0,1]$, we have ${{\mathsf {CMC}}} _{{\epsilon }}({{\mathcal {F}}})\ge {\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}} ({\epsilon })$.

• Efficiency-gap: For any ${\epsilon } \in (0,1]$, it holds that

  $$ \frac{\min _{{{\mathsf {A}}} \in {{\mathcal {A}}} _{{{\mathcal {F}}},T_{{{\mathcal {F}}}}}} ({\epsilon } \cdot {{\mathsf {Tm}}} ({{\mathsf {A}}}) \cdot {{\mathsf {Spc}}} ({{\mathsf {A}}}))}{ {{\mathsf {CMC}}} _{{\epsilon }}({{\mathcal {F}}})} \le {\varDelta _{{{\mathcal {F}}}}} ({\epsilon }), $$

  where ${{\mathcal {A}}} _{{{\mathcal {F}}},T_{{{\mathcal {F}}}}}$ is the set of deterministic sequential algorithms that run in at most $T_{{{\mathcal {F}}}}$ steps and correctly output ${f} ^{{{\mathsf {ip}}}}({x})$ for any ${{\mathsf {ip}}}$ and ${x}$.

2.2 Graphs and Pebbling Models

We use ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ to denote a directed acyclic graph (DAG) with ${N} = 2^{{n}}$ nodes, where ${\mathbb {V}} = {\left\{ 1, \dots , {N} \right\} }$. Let ${\mathsf {src}} ({\mathbb {G}}) \subseteq {\mathbb {V}}$ be the set of source nodes and ${\mathsf {sink}} ({\mathbb {G}}) \subseteq {\mathbb {V}}$ be the set of sink nodes. For a node $v \in {\mathbb {V}}$, ${\mathsf {pred}} (v) \,{:=}\, {\left\{ u: (u,v) \in {\mathbb {E}} \right\} }$ are the predecessor nodes of v, ${\mathsf {succ}} (v) \,{:=}\, {\left\{ w: (v, w) \in {\mathbb {E}} \right\} }$ is the set of v’s successors. We use ${\mathsf {indeg}} (v) \,{:=}\, |{\mathsf {pred}} (v)|$ to denote the indegree of v, and ${\mathsf {indeg}} ({\mathbb {G}})\,{:=}\,\max _{v\in {\mathbb {V}}} {\mathsf {indeg}} (v)$ is the indegree of ${\mathbb {G}}$. For a directed acyclic path ${P}$, the length of ${P}$ is the number of nodes it traverses. ${\mathsf {depth}} ({\mathbb {G}})$ is the length of the longest path in ${\mathbb {G}}$. For a nodes set $S\subseteq {\mathbb {V}}$, ${\mathbb {G}}-S$ is the DAG obtained from ${\mathbb {G}}$ by removing S and incident edges. Next, we review a useful graph-theoretic property called depth-robustness.

Definition 3

(Depth-Robustness [3]). A DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ is $({e}, {d})$-depth-robust if and only if ${\mathsf {depth}} ({\mathbb {G}}-S)\ge {d}$ for any $S \subseteq {\mathbb {V}}$ where $|S| \le {e}$.

Next, we define a stronger notion of depth-robustness called source-to-sink-depth-robustness. Intuitively, it means that after removing any nodes set with certain size, there still exists a long path from a source node to a sink node.

Definition 4

(Source-to-Sink-Depth-Robustness). A DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ is $({e}, {d})$-source-to-sink-depth-robust if and only if for any $S \subseteq {\mathbb {V}}$ where $|S| \le {e}$, ${\mathbb {G}}-S$ has a path (with length at least ${d}$) that starts from a source node of ${\mathbb {G}}$ and ends up in a sink node of ${\mathbb {G}}$.

We consider a pebbling game played on a DAG $({\mathbb {G}} = {\mathbb {V}}, {\mathbb {E}})$ [7]. We denote by a parallel pebbling on ${\mathbb {G}}$ as a sequence of pebbling configurations ${\mathsf {P}} = ({\mathsf {P}} _0, \dots , {\mathsf {P}} _{{t_{\mathsf {peb}}}})$ where ${\mathsf {P}} _0 = \emptyset$ and ${\mathsf {P}} _i \subseteq {\mathbb {V}}$ ($1 \le i \le {t_{\mathsf {peb}}}$). We define two properties for ${\mathsf {P}}$.

• Legality: We say ${\mathsf {P}}$ is legal if it satisfies follows: A pebble can be put on a node $v\in {\mathbb {V}}$ only if v is a source node or v’s predecessors were all pebbled at the end of the previous step, that is, for any $i \in [{t_{\mathsf {peb}}} ]$ and any $v \in {\mathsf {P}} _{i}\setminus {\mathsf {P}} _{i-1}$, it holds that ${\mathsf {pred}} (v) \subseteq {\mathsf {P}} _{i-1}$.⁸

• Successfulness: We say ${\mathsf {P}}$ is successful if it satisfies follows: Every sink node has been pebbled at least once, that is, for any $v \in {\mathsf {sink}} ({\mathbb {G}})$, there exists $i\in [{t_{\mathsf {peb}}} ]$ such that $v \in {\mathsf {P}} _{i}$.

We say ${\mathsf {P}}$ is a sequential pebbling if it further satisfies that $|{\mathsf {P}} _{i} \setminus {\mathsf {P}} _{i-1}|=1$ for every $i\in [{t_{\mathsf {peb}}} ]$. Next we define pebbling complexities of graphs.

Definition 5

(Complexity Measures [7]). For a pebbling strategy ${\mathsf {P}} = ({\mathsf {P}} _0=\emptyset , \dots , {\mathsf {P}} _{{t_{\mathsf {peb}}}})$, we define the cumulative complexity (and ST-complexity) of ${\mathsf {P}}$ to be

$$ {\mathsf {cc}} ({\mathsf {P}}) \,{:=}\, \sum ^{{t_{\mathsf {peb}}}}_{i=0} |{\mathsf {P}} _{i}|, \qquad \qquad {\mathsf {st}} ({\mathsf {P}}) \,{:=}\, {t_{\mathsf {peb}}} \cdot \max _{i\in [{t_{\mathsf {peb}}} ]}(|{\mathsf {P}} _{i}|). $$

For a DAG ${\mathbb {G}} =({\mathbb {V}}, {\mathbb {E}})$, let ${{\mathcal {P}} ^{\Vert }} ({\mathbb {G}})$ be the set of parallel pebblings of ${\mathbb {G}}$ (that are legal and successful); for any $t\in {\mathbb {N}}$, let ${{\mathcal {P}}} _{t}({\mathbb {G}})$ be the set of sequential pebblings of ${\mathbb {G}}$ that (are legal and successful) and takes at most t steps. We define the cumulative complexity (and ST-complexity) of ${\mathbb {G}}$ to be

$$ {\mathsf {cc}} ({\mathbb {G}}) \,{:=}\, \min _{{\mathsf {P}} \in {{\mathcal {P}} ^{\Vert }} ({\mathbb {G}})} {\mathsf {cc}} ({\mathsf {P}}), \qquad \qquad {\mathsf {st}} ({\mathbb {G}},t) \,{:=}\, \min _{{\mathsf {P}} \in {{\mathcal {P}}} _{t}({\mathbb {G}})} {\mathsf {st}} ({\mathsf {P}}). $$

There is a tight relation between depth-robustness and cumulative complexity.

Lemma 1

([3]). Let ${\mathbb {G}}$ be an $({e},{d})$-depth-robust DAG, then ${\mathsf {cc}} ({\mathbb {G}})\ge {e} \cdot {d}$.

2.3 Graph-Based iMHFs from Labeling Functions

For a DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ with ${N} = 2^{{n}}$ nodes, we index the nodes set ${\mathbb {V}} = {\left\{ 1, \dots , {N} \right\} }$ by a topological order so that ${\mathsf {src}} ({\mathbb {G}}) = \{1, \dots , {n_{s}} \}$ and ${\mathsf {sink}} ({\mathbb {G}})=\{{N}-{n_{t}} +1,\dots , {N} \}$. Fix ${W} =2^{{w}}$, ${\delta } \,{:=}\,{\mathsf {indeg}} ({\mathbb {G}})$ and let ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ be the set of ideal primitives. Denote by

$$ {{\mathcal {H}}} = {{\mathcal {H}}} _{{\delta },{w}} = {\left\{ {\mathsf {lab}^{{{\mathsf {ip}}}}_{{\gamma }}}:{\{0,1\}} ^{{\gamma } {W}}\rightarrow {\{0,1\}} ^{{W}}\right\} } _{{\gamma } \in [{\delta } ], {{\mathsf {ip}}} \in {{\mathbb {IP}}}} $$

a family of labeling functions. We define a family of graph functions ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}}}} = \{{{\mathsf {F}} ^{{{\mathsf {ip}}}}_{{\mathbb {G}},{{\mathcal {H}}}}} : {\{0,1\}} ^{{n_{s}} {W}} \rightarrow {\{0,1\}} ^{{n_{t}} {W}} \}_{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$ based on ${\mathbb {G}}$ and ${{\mathcal {H}}}$: For an input ${\mathbf {x}} = ({x} _1, \dots , {x} _{{n_{s}}})\in {\{0,1\}} ^{{n_{s}} {W}}$, denote ${\ell } _{i} \,{:=}\, {\mathsf {lab}^{{{\mathsf {ip}}}}_{1}} ({x} _{i})$ as the label of the ith source ($1\le i\le {n_{s}}$), we recursively define the label of $v\in [{N} ]$ as

$$ {\ell } _{v} \,{:=}\, {\mathsf {lab}^{{{\mathsf {ip}}}}_{{\gamma }}} ({\ell } _{v_1}, \dots , {\ell } _{v_{{\gamma }}}) $$

where $(v_1, \dots , v_{{\gamma }})$ are the predecessors of v. The output ${{\mathsf {F}} ^{{{\mathsf {ip}}}}_{{\mathbb {G}},{{\mathcal {H}}}}} ({x})$ is defined as the concatenation of sinks’ labels, that is, $({\ell } _{{N}-{n_{t}} +1}\Vert \dots \Vert {\ell } _{{N}})$.

If ${n_{s}} =|{\mathsf {src}} ({\mathbb {G}})|>1$, we implicitly assume that the input vector ${\mathbf {x}} = ({x} _1, \dots , {x} _{{n_{s}}})$ has no overlapping blocks (and we call it a non-colliding input vector), that is, for any $i,j\in {\mathbb {N}}$ such that $i\ne j$, we have ${x} _i\ne {x} _{j}$. This constraint is necessary for preventing the adversary from easily saving memory. For example, if the blocks in the input vector are identical, the adversary only needs to store a single block instead of the entire input vector. The constraint/assumption is also reasonable as we can re-randomize the original input using a random oracle ${\mathsf {RO}}:{\{0,1\}} ^{{n_{s}} {W}}\rightarrow {\{0,1\}} ^{{n_{s}} {W}}$, and the output blocks will be distinct with overwhelming probability when ${n_{s}} \ll 2^{{W}/2}$.

Remark 3

(Graph constraint). In the following context, the graphs we are concerned with should satisfy certain properties. In particular, each 2-indegree DAG ${\mathbb {G}} = ({\mathbb {V}},{\mathbb {E}})$ considered in Sect. 3 should be predecessors-distinct, that is, for any two distinct vertices $u,v\in {\mathbb {V}} \setminus {\mathsf {src}} ({\mathbb {G}})$, we have ${\mathsf {pred}} (u) \ne {\mathsf {pred}} (v)$. Looking ahead, this constraint is used to prevent non-source nodes label collisions. Additionally, each ${\delta }$-indegree DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ considered in Sect. 4 satisfies a property called first-predecessor-distinctness, that is, there exists a map from each non-source node $v\in {\mathbb {V}} \setminus {\mathsf {src}} ({\mathbb {G}})$ to a single node $\mathsf {fpre}(v)\in {\mathsf {pred}} (v)$, so that for any two distinct vertices $u,v\in {\mathbb {V}} \setminus {\mathsf {src}} ({\mathbb {G}})$, we have $\mathsf {fpre}(u)\ne \mathsf {fpre}(v)$. Looking ahead, this constraint is used to guarantee that the 2-indegree bootstrapped graph ${\mathsf {Ext}_{{\delta },{W}}({\mathbb {G}})}$ built upon ${\mathbb {G}}$ is predecessors-distinct. We stress that practical DAG constructions usually contain a subpath that traverses all of the vertices, and thus are both first-predecessor-distinct and predecessors-distinct.⁹

3 MHFs from Small-Block Labeling Functions

In this section, we construct a family of graph-based iMHFs based on what we refer to as a small-block labeling function, i.e., a simple hash function based on an ideal primitive, which preserves its block length. (Note that this notion is introduced for modularity reason – we could define our designs directly as depending on a primitive.) In Sect. 3.1, we define and construct of efficient small-block labeling functions from primitives, and in Sect. 3.2, we prove that the constructions satisfies the required properties. Finally, in Sect. 3.3, we construct iMHFs from small-block labeling functions.

3.1 Small-Block Labeling Functions: Definition and Construction

Definition 6

(Small-Block Labeling Functions). For an ideal primitive ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ with block length ${L} =2^{{\ell }}$, we say

$$ {{\mathcal {H}}} _{{\mathsf {fix}}} = {\left\{ {\mathsf {flab}^{{{\mathsf {ip}}}}}:{\left\{ {\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}\right\} } \rightarrow {\{0,1\}} ^{{L}}\right\} } _{ {{\mathsf {ip}}} \in {{\mathbb {IP}}}}$$

is a family of ${\beta }$-small-block labeling functions if it has the following property.

• ${\beta } (\cdot ,\cdot )$ -pebbling reducibility: For any ${\epsilon } \in (0,1]$ and 2-indegree (predecessors-distinct¹⁰) DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$,¹¹ let ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\mathsf {fix}}}}}$ be the graph function built upon ${\mathbb {G}}$ and ${{\mathcal {H}}} _{{\mathsf {fix}}}$. We have

  $$ {{\mathsf {CMC}}} _{{\epsilon }}({{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\mathsf {fix}}}}}) \ge {\beta } ({\epsilon }, \log |{\mathbb {V}} |) \cdot {\mathsf {cc}} ({\mathbb {G}}), $$

  where ${\mathsf {cc}} ({\mathbb {G}})$ is the cumulative complexity of ${\mathbb {G}}$ (Definition 5).

Next, we show how to construct small-block labeling functions from ideal primitives. Our main contribution is a construction from a random permutation, which can be instantiated from fixed-key AES. For completeness, we also present constructions from ideal ciphers and compression functions. We fix the input domain to be ${\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}$ and the output space to be ${\{0,1\}} ^{{L}}$, and denote as ${{\mathbb {RP}}}$, ${{\mathbb {IC}}}$, ${{\mathbb {CF}}}$ the random permutations, ideal ciphers, and compression functions, respectively.

• 1. Given any ${{\mathsf {rp}}} \in {{\mathbb {RP}}}$, we define the labeling function ${\mathsf {flab}^{{{\mathsf {rp}}}}} (\cdot )$ as follows: For any input ${x} \in {\{0,1\}} ^{{L}}$, the output is ${\mathsf {flab}^{{{\mathsf {rp}}}}} ({x})\,{:=}\,{{\mathsf {rp}}} ({x})\oplus {x}$; for any input $({x} _{1},{x} _{2})\in {\{0,1\}} ^{2{L}}$, denote as ${x} ^{*}\,{:=}\,{x} _{1}\oplus {x} _{2}\in {\{0,1\}} ^{{L}}$, the output is ${\mathsf {flab}^{{{\mathsf {rp}}}}} ({x} _{1},{x} _{2})\,{:=}\,{{\mathsf {rp}}} ({x} ^{*})\oplus {x} ^{*}$.

• 2. Given any ${{\mathsf {ic}}} \in {{\mathbb {IC}}}$, we define the labeling function ${\mathsf {flab}^{{{\mathsf {ic}}}}} (\cdot )$ as follows: For any input ${x} \in {\{0,1\}} ^{{L}}$, the output is ${\mathsf {flab}^{{{\mathsf {ic}}}}} ({x})\,{:=}\,{{\mathsf {ic}}} (\bot ,{x})\oplus {x}$; for any input $(k,{x})\in {\{0,1\}} ^{2{L}}$, the output is ${\mathsf {flab}^{{{\mathsf {ic}}}}} (k,{x})\,{:=}\,{{\mathsf {ic}}} (k,{x})\oplus {x}$.

• 3. Given any ${{\mathsf {cf}}} \in {{\mathbb {CF}}}$, we define the labeling function ${\mathsf {flab}^{{{\mathsf {cf}}}}} (\cdot )$ as follows: For any input ${x} \in {\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}$, the output is ${\mathsf {flab}^{{{\mathsf {cf}}}}} ({x})\,{:=}\,{{\mathsf {cf}}} ({x})$.

Note that all of the above constructions are highly efficient as they call the ideal-primitive only once. Next we show that the constructions are pebbling reducible.

Remark 4

The construction for compression functions is interesting, even in view of prior work, because of the fact that prior work included the node identity into the hash-function input, thus effectively requiring $2{L} +\log {N}$-bit inputs, whereas here we can get away with $2{L}$.

3.2 Small-Block Labeling Functions: Pebbling Reducibility

In this section, we show that the labeling functions constructed in Sect. 3.1 satisfy pebbling reducibility, via the following three theorems.

Theorem 1

Assume an adversary can make no more than ${{\mathsf {q}}} _{1}$ oracle calls and ${{\mathsf {q}}} _{2}$ output calls such that ${{\mathsf {q}}} _{1}+{{\mathsf {q}}} _{2}={{\mathsf {q}}} =2^{{L}/4}$. ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {cf}}}}} \}_{{{\mathsf {cf}}} \in {{\mathbb {CF}}}}$ built upon compression function ${{\mathbb {CF}}}$ is ${\beta } (\cdot ,\cdot )$-pebbling reducible, where for all ${\epsilon } \ge 3\cdot 2^{-{L}/8}$ and ${N} \le 2^{{L}/8}$, it holds that ${\beta } ({\epsilon }, \log {N}) \ge \frac{{\epsilon } {L}}{8}$.

Theorem 2

Assume an adversary can make no more than ${{\mathsf {q}}} _{1}$ oracle calls and ${{\mathsf {q}}} _{2}$ output calls such that ${{\mathsf {q}}} _{1}+{{\mathsf {q}}} _{2}={{\mathsf {q}}} =2^{{L}/4}$. ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {ic}}}}} \}_{{{\mathsf {ic}}} \in {{\mathbb {IC}}}}$ built upon ideal cipher ${{\mathbb {IC}}}$ is ${\beta } (\cdot ,\cdot )$-pebbling reducible, where for all ${\epsilon } \ge 3\cdot 2^{-{L}/8}$ and ${N} \le 2^{{L}/8}$, it holds that ${\beta } ({\epsilon }, \log {N}) \ge \frac{{\epsilon } {L}}{8}$.

Theorem 3

Assume an adversary can make no more than ${{\mathsf {q}}} _{1}$ oracle calls and ${{\mathsf {q}}} _{2}$ output calls such that ${{\mathsf {q}}} _{1}+{{\mathsf {q}}} _{2}={{\mathsf {q}}} =2^{{L}/8}$. ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {rp}}}}} \}_{{{\mathsf {rp}}} \in {{\mathbb {RP}}}}$ built upon random permutation ${{\mathbb {RP}}}$ is ${\beta } (\cdot ,\cdot )$-pebbling reducible, where for all ${\epsilon } \ge 3\cdot 2^{-{L}/10}$ and ${N} \le 2^{{L}/10}$, it holds that ${\beta } ({\epsilon }, \log {N}) \ge \frac{{\epsilon } {L}}{40}$.

Next we present the proofs for Theorems 1, 2 and 3. First, we introduce some notation for graph labeling, then we highlight the proof techniques and introduce the notion of ex-post-facto pebbling in the ideal primitive model. Finally, we provide the formal proof.

Fix ideal primitive ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$,¹² input vector ${\mathbf {x}}$ and any graph ${\mathbb {G}} =({\mathbb {V}}, {\mathbb {E}})$. For a primitive ${{\mathsf {ip}}} \in {{\mathbb {IP}}}$ and any node $v\in {\mathbb {V}}$, we denote as ${\ell } _{v}$ the graph label of v. If v is a source, ${\mathsf {prelab}} (v)$ is the corresponding input label $x_{v}$. If v is a non-source node, we define ${\mathsf {prelab}} (v)$ based on the type of the ideal primitive:

• If ${{\mathbb {IP}}} ={{\mathbb {RP}}}$, we define ${\mathsf {prelab}} (v)$ as the exclusive-or sum of v’s parents’ $\ell$-labels.

• If ${{\mathbb {IP}}} ={{\mathbb {IC}}}/{{\mathbb {CF}}}$, we define ${\mathsf {prelab}} (v)$ as the concatenation of v’s parents’ $\ell$-labels.

Similarly, for every node $v\in {\mathbb {V}}$, we define ${\mathsf {aftlab}} (v)$ based on the type of the ideal primitive:

• If ${{\mathbb {IP}}} ={{\mathbb {RP}}}/{{\mathbb {CF}}}$, we define ${\mathsf {aftlab}} (v) = {{\mathsf {ip}}} ({\mathsf {prelab}} (v))$.

• If ${{\mathbb {IP}}} ={{\mathbb {IC}}}$ and v has only one parent, we define ${\mathsf {aftlab}} (v) = {{\mathsf {ip}}} (\bot , {\mathsf {prelab}} (v))$. Otherwise if v has two parents, denote as ${\mathsf {prelab}} (v) = (y_1, y_2)$ (where $y_1,y_2 \in \{0,1\}^{{L}}$ are $\ell$-labels of v’s parents), we define ${\mathsf {aftlab}} (v)$ as $(y_1, {{\mathsf {ip}}} (y_1,y_2))$.

In the following context, we abuse the notation a bit in that if ${\mathsf {prelab}} (v)$ (or ${\mathsf {aftlab}} (v)$) is an ${L}$-bit string and ${{\mathsf {ip}}}$ is an ideal cipher, we use ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ (or ${{\mathsf {ip}}} ^{-1}({\mathsf {aftlab}} (v))$) to denote ${{\mathsf {ip}}} (\bot , {\mathsf {prelab}} (v))$ (or ${{\mathsf {ip}}} ^{-1}(\bot ,{\mathsf {aftlab}} (v))$). Moreover, for an ideal cipher query with input ${x_{c}} =(\bot , x)$, we say $x_c = {\mathsf {prelab}} (v)$ (or $x_c = {\mathsf {aftlab}} (v)$) if and only if $x = {\mathsf {prelab}} (v)$ (or $x = {\mathsf {aftlab}} (v)$), respectively.

We remark that ${\mathsf {prelab}} (v)$ (and ${\mathsf {aftlab}} (v)$) are more than just single labels, they are used to identify the node from a query input to the ideal primitive.

Similar as in [7], the proof idea is to transform any algorithm execution ${{\mathsf {A}}}$ into an ex-post-facto pebbling, and argue that the cumulative memory complexity of ${{\mathsf {A}}}$ is proportional to the cumulative complexity of the pebbling. This is proved by mapping each node $v\in {\mathbb {V}}$ to an ideal-primitive entry $({\mathsf {prelab}} (v),{{\mathsf {ip}}} ({\mathsf {prelab}} (v)))$, and argue that for each round ${i} \in {\mathbb {N}}$, the input state ${\sigma } _{{i}}$ should have large size as it is an encoding for many ideal-primitive entries. In particular, for every node v in the ${i}$th pebbling configuration, ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ (and ${\ell } _{v}$) can be decoded from an oracle-call input in the partial execution ${{\mathsf {A}}} ({\sigma } _{{i}})$. Here we generalize the technique of [7] so that it works even if:

• 1. The ideal-primitive input ${\mathsf {prelab}} (v)$ contains no explicit information of the node index v. (Note that in previous work [7], ${\mathsf {prelab}} (v)$ has v as a prefix.)

• 2. The adversary can make inverse queries to the ideal primitive.

• 3. The input length of the primitive is much shorter than the actual input length of the labeling function.

Similar as in [7], we define a notion called ex-post-facto pebbling in the ideal primitive model. Fix ideal primitive ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$, input vector ${\mathbf {x}}$, DAG ${\mathbb {G}} =({\mathbb {V}}, {\mathbb {E}})$. For any ${{\mathsf {ip}}} \in {{\mathbb {IP}}}$, randomness ${r}$, and the execution trace ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r})$ (that runs for ${t_{\mathsf {peb}}} +1$ rounds), we turn the trace into an ex-post-facto pebbling

$$ {{\mathcal {P}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}, {r}))= ({\mathsf {P}} _{0}=\emptyset ,\dots ,{\mathsf {P}} _{{t_{\mathsf {peb}}}}). $$

For each oracle call/query that asks for the ideal-primitive value on input ${x_{c}}$, we say that the call is a correct call for a node $v\in {\mathbb {V}}$ if and only if ${x_{c}}$ matches ${\mathsf {prelab}} (v)$ and the call is forward, or ${x_{c}}$ matches ${\mathsf {aftlab}} (v)$ and the call is an inverse call. We define the ex-post-facto pebbling configurations in reverse order. For ${i}$ from ${t_{\mathsf {peb}}}$ to 1, denote as ${\sigma } _{{i}}$ the input state of round ${i} +1$ and ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ the partial execution of ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r})$ after round ${i}$, the pebbling configuration ${\mathsf {P}} _{{i}}$ is defined as follows. (In the following context, by round ${\gamma }$, we always mean the ${\gamma }$-th round in the execution ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}, {r})$.)

• 1. Critical Calls: We sort the output/ideal primitive calls of ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ in chronological order¹³ and determine whether they are critical calls.

  • An output call (in round ${\gamma } > {i}$) with label $(v,{\ell } _{v})$ is a critical call for $v\in {\mathbb {V}}$ if and only if v is a sink and in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$, no correct call for v appeared before round ${\gamma }$.

  • An ideal-primitive call (in round ${\gamma } > {i}$) is a critical call for a node $u\in {\mathbb {V}}$ if and only if the following conditions both hold: (i) the ideal-primitive call is a correct call for a successor node $v\in {\mathsf {succ}} (u)$ and in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$, no correct call for u appeared before round ${\gamma }$; (ii) v is in ${\mathsf {P}} _{{\gamma }}$.

• 2. Pebbling Configuration: A node $v\in {\mathbb {V}}$ is included into the pebbling configuration ${\mathsf {P}} _{{i}}$ if and only if both of the following conditions hold:

  • There is at least one critical call for v in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$.

  • There is at least one correct call for v between round 1 and round ${i}$ (inclusively).¹⁴

In a critical call, the algorithm provides the information of a graph label without recomputing, hence the call is useful in extracting ideal-primitive entries. On a side note, by definition of critical call and ex-post-facto pebbling, for any round ${i}$, we might possibly put a node u into ${\mathsf {P}} _{{i}}$ only if u is a sink or one of its successor $v\in {\mathsf {succ}} (u)$ is in ${\mathsf {P}} _{{\gamma }}$ for some ${\gamma } > {i}$.

Proof

(of Theorems 1, 2 and 3). Fix ideal primitive type ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$, input vector ${\mathbf {x}}$, adversary ${{\mathsf {A}}}$, and any graph ${\mathbb {G}} =({\mathbb {V}}, {\mathbb {E}})$, the proof consists of the following four steps.

First, we show that with probability at least $1-{{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})$ (over the choice of the ideal primitive), the pre-labels $\{{\mathsf {prelab}} (v)\}_{v\in {\mathbb {V}}}$ are all distinct.¹⁵

Lemma 2

Fix ideal primitive ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ (with block length ${L}$), predecessors-distinct DAG ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ (with ${n_{s}}$ source nodes), non-colliding input vector ${\mathbf {x}} \in {\{0,1\}} ^{{n_{s}} {L}}$,¹⁶ and ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {ip}}}}} \}_{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$ constructed in Sect. 3. With probability at least $1-{{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})$ (over the uniformly random choice of ${{\mathsf {ip}}}$), the graph labeling satisfies that the pre-labels $\{{\mathsf {prelab}} (v)\}_{v\in {\mathbb {V}}}$ are all distinct. Here ${{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {CF}}}) = |{\mathbb {V}} |^{2}/2^{{L} +1}$ and ${{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IC}}})={{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {RP}}})=|{\mathbb {V}} |^{2}/2^{{L}}$.

Proof

The proof is deferred to full version.    $\square$

The property in Lemma 2 is useful in determining the node index v when one sees an ideal-primitive query related to v. Moreover, it guarantees that each node v maps to a unique ideal-primitive input entry ${\mathsf {prelab}} (v)$.

Next, we show that with high probability (over the uniform choices of the ideal primitive ${{\mathsf {ip}}}$ and random coins ${r}$), the ex-post-facto pebbling ${{\mathcal {P}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}, {r})) =({\mathsf {P}} _{0}=\emptyset , \dots , {\mathsf {P}} _{{t_{\mathsf {peb}}}})$ for ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r})$ is legal, and thus

$$ \sum _{i=0}^{{t_{\mathsf {peb}}}} |{\mathsf {P}} _i| \ge {\mathsf {cc}} ({\mathbb {G}}) $$

as long as the pebbling is successful.

Before presenting the lemma, we prove a claim that will be useful in many places.

Claim 1

Fix any execution ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r})$ (with input states ${\sigma } _0, {\sigma } _1, \dots$) whose ex-post-facto pebbling is ${{\mathcal {P}}} ({{\mathsf {A}}})= ({\mathsf {P}} _{0},\dots ,{\mathsf {P}} _{{t_{\mathsf {peb}}}})$. For any $i \in [{t_{\mathsf {peb}}} ]$ and any vertex $v\in {\mathsf {P}} _{i}\setminus {\mathsf {P}} _{i-1}$, it holds that there is a correct call for v in round i.

Proof

The proof is deferred to full version.    $\square$

Lemma 3

Fix ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ (with block length ${L}$), predecessors-distinct DAG ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ (with ${n_{s}}$ source nodes), non-colliding input vector ${\mathbf {x}} \in {\{0,1\}} ^{{n_{s}} {L}}$, algorithm ${{\mathsf {A}}}$, and ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {ip}}}}} \}_{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$ constructed in Sect. 3. With probability at least $1-{{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})-{{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {IP}}})$ (over the uniformly random choices of ${{\mathsf {ip}}}$ and ${{\mathsf {A}}}$’s internal coins ${r}$), the pre-labels are distinct and the ex-post-facto pebbling for ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r})$ is legal. Here ${{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})$ is the same as in Lemma 2 and ${{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {CF}}})={{\mathsf {q}}} \cdot |{\mathbb {V}} |/2^{{L}-1}$, ${{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {IC}}})={{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {RP}}})= {{\mathsf {q}}} \cdot |{\mathbb {V}} |/2^{{L}-2}$, where ${{\mathsf {q}}}$ is an upper bound on the number of calls made by ${{\mathsf {A}}}$.

Proof

The proof is deferred to full version.    $\square$

Next, we build the connection between the state size and the size of the pebbling configuration. In particular, we show that with high probability, the input state size $|{\sigma } _{{i}}|$ is proportional to $|{\mathsf {P}} _{{i}}|$ for all $i\in {\mathbb {N}}$.

Lemma 4

Fix ${L} =2^{{\ell }}$, predecessors-distinct DAG ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ (with ${n_{s}}$ source nodes), non-colliding input vector ${\mathbf {x}} \in {\{0,1\}} ^{{n_{s}} {L}}$, algorithm ${{\mathsf {A}}}$ (that makes at most ${{\mathsf {q}}}-1$ calls), and ${{\mathcal {H}}} _{{\mathsf {fix}}}=\{{\mathsf {flab}^{{{\mathsf {ip}}}}} \}_{{{\mathsf {ip}}} \in {{\mathbb {IP}}}}$ constructed in Sect. 3. Set values ${{\beta } _{{{\mathbb {CF}}}}} \,{:=}\,\lfloor {L}-2\log {{\mathsf {q}}}-\log |{\mathbb {V}} |-\log 3\rfloor$, ${{\beta } _{{{\mathbb {IC}}}}} \,{:=}\,\lfloor {L}-1-2\log {{\mathsf {q}}}-\log |{\mathbb {V}} |-\log 3\rfloor$, and ${{\beta } _{{{\mathbb {RP}}}}} \,{:=}\,\lfloor \frac{{L}}{2}-1-2\log {{\mathsf {q}}}-\log |{\mathbb {V}} |-\log 3\rfloor$. For any ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$ and ${\lambda } \in {\mathbb {N}}$, define $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ as the event where the following three conditions all hold:

• 1. The pre-labels are distinct from each other.

• 2. The ex-post-facto pebbling $({\mathsf {P}} _{0}, {\mathsf {P}} _{1}, \dots , {\mathsf {P}} _{{t_{\mathsf {peb}}}})$ for ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}};{r})$ is legal.

• 3. There exists ${i} \in {\mathbb {N}}$ such that $|{\sigma } _{{i}}|<|{\mathsf {P}} _{{i}}| \cdot {{\beta } _{{{\mathbb {IP}}}}}-{\lambda }$, where ${\sigma } _{{i}}$ denotes the input state for round ${i} +1$ and ${\mathsf {P}} _{{i}}$ denotes the pebbling configuration in round ${i}$.

It holds that $\Pr [ \textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}} ] \le 2^{-{\lambda }}$ for all ${\lambda } \in {\mathbb {N}}$, where the probability is taken over the choice of and random coins of ${{\mathsf {A}}}$.

Proof

Without loss of generality we fix ${r}$ to be the optimal random coins of ${{\mathsf {A}}}$ that maximizes $\Pr [\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}} ]$. We will show a predictor P (that hardwires ${r}$ and has oracle access to ${{\mathsf {ip}}}$), such that if $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ happens (which implies $|{\sigma } _{{i}}|<|{\mathsf {P}} _{{i}}| \cdot {{\beta } _{{{\mathbb {IP}}}}}-{\lambda }$ for some ${i} \in {\mathbb {N}}$), there will be a hint h with no more than $|{\mathsf {P}} _{{i}}|\cdot {L}- {\lambda }$ (and $|{\mathsf {P}} _{{i}}|\cdot ({L}-1) - {\lambda }$ when ${{\mathbb {IP}}} ={{\mathbb {IC}}}/{{\mathbb {RP}}}$) bits, where P(h) can predict $|{\mathsf {P}} _{{i}}|$ ideal primitive entries correctly. Thus by the compression arguments that ideal primitives cannot be compressed (i.e., Lemmas 9 and 10), $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ happens with probability no more than $2^{-{\lambda }}$ and the lemma holds. Next we describe the hint h and the predictor P.

For any choice of ${{\mathsf {ip}}} \in {{\mathbb {IP}}}$, if event $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ happens, there exists a round ${i} \in {\mathbb {N}}$ such that $|{\sigma } _{{i}}|<|{\mathsf {P}} _{{i}}| \cdot {{\beta } _{{{\mathbb {IP}}}}}-{\lambda }$, where ${\sigma } _{{i}}$ is the input state of round ${i} +1$ and ${\mathsf {P}} _{{i}} = ({v} _{1}, {v} _{2},\dots ,{v} _{ |{\mathsf {P}} _{{i}}|})$ is the ex-post-facto pebbling configuration. The hint consists of the state ${\sigma } _{{i}}$ and the following helper information. (In the following context, if not describe explicitly, by critical call, we always mean a critical call in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$.)

• A sequence $Q_{{i}} = ({\mathsf {id}} _{1},{\mathsf {id}} _{2}, \dots , {\mathsf {id}} _{|{\mathsf {P}} _{{i}}|}) \in [{{\mathsf {q}}}-1]^{|{\mathsf {P}} _{{i}}|}$, where ${\mathsf {id}} _{j}$ ($1\le j\le |{\mathsf {P}} _{{i}}|$) is the index of the first critical call for ${v} _{j}\in {\mathsf {P}} _{{i}}$ in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$. (Recall that we sort the calls in chronological order, and assume an implicit order for the calls in the same round.)

• A nodes sequence $W_{{i}} = ({w} _{1}, {w} _{2},\dots ,{w} _{|{\mathsf {P}} _{{i}}|})$, where ${w} _{j}={v} _{j}$ ($1\le j\le |{\mathsf {P}} _{{i}}|$) if the ${\mathsf {id}} _{j}$-th call is an output call; otherwise, if the ${\mathsf {id}} _{j}$-th call is a correct call for some successor of ${v} _{j}$, then ${w} _{j}$ is assigned as the corresponding successor node.

• A sequence $B_{{i}} = ({b} _{1},{b} _{2},\dots ,{b} _{|{\mathsf {P}} _{{i}}|})$, where ${b} _{j}\in \{0,1,2\}$ is used to indicate the relation between ${w} _{j}$ and ${v} _{j}$. In particular, ${w} _{j}={v} _{j}$ if ${b} _{j}=0$, otherwise ${v} _{j}$ is the ${b} _{j}$-th predecessor of ${w} _{j}$.

• A sequence $C_{{i}} = ({\mathsf {cid}} _{1},{\mathsf {cid}} _{2},\dots ,{\mathsf {cid}} _{|{\mathsf {P}} _{{i}}|})$, where ${\mathsf {cid}} _{j}=0$ ($1\le j\le |{\mathsf {P}} _{{i}}|$) if there is no correct call for ${v} _{j}\in {\mathsf {P}} _{{i}}$ in the trace ${{\mathsf {A}}} ({\sigma } _{{i}})$, otherwise ${\mathsf {cid}} _{j}$ is the query index of the first correct call for ${v} _{j}$.

• If ${{\mathbb {IP}}} ={{\mathbb {RP}}}$, the hint includes an extra sequence $H_{{i}}=({h} _{1},{h} _{2},\dots ,{h} _{|{\mathsf {P}} _{{i}}|})$, where ${h} _{j}$ ($1\le j\le |{\mathsf {P}} _{{i}}|$) is the label ${\ell } _{{v} _{j}}$ if there exists some $k>j$ such that ${\mathsf {id}} _{j} = {\mathsf {id}} _{k}$ (i.e., another node ${v} _{k}\in {\mathsf {P}} _{{i}}$ has the same first critical call), otherwise ${h} _{j}$ is set as empty¹⁷. We see that there are at most $\lfloor |{\mathsf {P}} _{{i}}|/2\rfloor$ non-empty values in the sequence, as any ideal-primitive call can be a critical call for at most two vertices.

Note that we can easily recover the configuration ${\mathsf {P}} _{{i}}$ from the hint $W_{{i}}$ and $B_{{i}}$. The size of the hint is no more than $\mathsf {len}_{{{\mathbb {IP}}}}\,{:=}\,|{\mathsf {P}} _{{i}}|\cdot {L}- {\lambda }$ (and $\mathsf {len}_{{{\mathbb {IP}}}}\,{:=}\,|{\mathsf {P}} _{{i}}|\cdot ({L}-1) - {\lambda }$ when ${{\mathbb {IP}}} ={{\mathbb {IC}}}/{{\mathbb {RP}}}$) bits given the setting of ${{\beta } _{{{\mathbb {IP}}}}}$.

Given any input the predictor P parses the input into ${\sigma } _{{i}}$, $Q_{{i}}$, $W_{{i}}$, $B_{{i}}$, $C_{{i}}$ and $H_{{i}}$ as mentioned before¹⁸, and recovers the pebbling configuration ${\mathsf {P}} _{{i}}$. Then P runs the partial execution ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ and attempts to predict $({\mathsf {prelab}} (v),{{\mathsf {ip}}} ({\mathsf {prelab}} (v)))$ for every $v\in {\mathsf {P}} _{i}$ without querying ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$. In the following context, if not describe explicitly, by critical call, we always mean a critical call in the trace ${{{\mathsf {A}}} ({\sigma } _{{i}})}$.

When simulating ${{{\mathsf {A}}} ({\sigma } _{{i}})}$, the predictor uses the following approach to determine if an ideal-primitive call is a correct call for a node v: The predictor keeps track of the labels ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ for every $v\in {\mathbb {V}}$. Moreover, after knowing the labels of v’s predecessors, the predictor updates ${\mathsf {prelab}} (v)$ accordingly. Given an ideal-primitive call from ${{\mathsf {A}}}$, P determines call correctness by checking the following cases sequentially:

• If P knows from hint $Q_{{i}}$ that the call is the first critical call for some node $v\in {\mathsf {P}} _{{i}}$, then the predictor knows that it is also a correct call for some node ${w}$, where ${w}$ can be extracted from the hint $W_{{i}}$.

• If the call is the first correct call¹⁹ for some node $v\in {\mathsf {P}} _{{i}}$, then P will know it from the hint $C_{{i}}$.

• The call is a forward call. Then the predictor checks if there exists a node $v\in {\mathbb {V}}$ where ${\mathsf {prelab}} (v)$ was updated and ${\mathsf {prelab}} (v)$ matches the call input ${x_{c}}$. If so, P asserts that it is a correct call for v.

• ${{\mathbb {IP}}} = {{\mathbb {IC}}}/{{\mathbb {RP}}}$ and the call is an inverse call. Then the predictor first checks if there is a node $v\in {\mathbb {V}}$ where ${\mathsf {aftlab}} (v)$ was updated and ${\mathsf {aftlab}} (v)$ matches the call input ${x_{c}}$. If no such v exists, P queries the oracle, and checks if the answer is consistent with some updated ${\mathsf {prelab}} (v)$ ($v\in {\mathbb {V}}$).

• If one of the above checks succeed, then after recognizing the correct call for v, P updates ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ accordingly.

Claim 2

Fix execution ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}};{r})$ and round ${i}$, suppose the pre-labels are distinct, and the ex-post-facto pebbling $({\mathsf {P}} _{0}, \dots , {\mathsf {P}} _{{t_{\mathsf {peb}}}})$ is legal. For any round ${\gamma } >{i}$, assume the predictor successfully extracted $\ell$-labels for all (first) critical calls (in ${{{\mathsf {A}}} ({\sigma } _{{i}})}$) between round ${i}$ and round ${\gamma }$. Then for any vertex $v\in {\mathsf {P}} _{{i}}\cup \dots \cup {\mathsf {P}} _{{\gamma }}$, and any correct call for v in round ${\gamma }$ (denote the call as C(v)), the predictor will correctly recognize the call C(v) when simulating ${{{\mathsf {A}}} ({\sigma } _{{i}})}$.

Proof

The proof is deferred to full version.    $\square$

Next we show how to simulate ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ and predict ideal-primitive entries.

The predictor simulates ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ (which corresponds to the partial execution of ${{\mathsf {A}}}$ after round ${i}$) and keeps track of the labels ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ for every $v\in {\mathbb {V}}$. For each round ${\gamma } > {i}$, after receiving the calls from ${{\mathsf {A}}}$, the predictor P does follows sequentially.

• 1. Handling critical calls: P first enumerates node ${v} _{j}\in {\mathsf {P}} _{{i}}$ according to reverse topological order²⁰ and checks the following: If the ${\mathsf {id}} _{j}$-th call (i.e. ${v} _{j}$’s first critical call) is in round ${\gamma }$ and ${\ell } _{{v} _{j}}$ is unknown yet, the predictor uses the hint to extract the label ${\ell } _{{v} _{j}}$. The extraction from a critical output call is trivial, thus we assume that the call is an ideal-primitive call. From the hint, the predictor knows that it is a correct ideal primitive call for a node ${w} _{j}\in {\mathsf {succ}} ({v} _{j})$ where ${w} _{j}$ can be extracted from the hint $W_{{i}}$. (Note that ${w} _{j}\in {\mathsf {P}} _{{\gamma }}$ by definition of critical calls.) The predictor first extracts ${\mathsf {prelab}} ({w} _{j})$ from the call input/output:

  • If the call is forward, ${\mathsf {prelab}} ({w} _{j})$ can be identified from the call input.

  • If ${w} _{j}\in {\mathsf {P}} _{{i}}$ and the call is an inverse call, since P chooses nodes in ${\mathsf {P}} _{{i}}$ according to reverse topological order, and in ${{{\mathsf {A}}} ({\sigma } _{{i}})}$ the first critical call for ${w} _{j}$ appears no later than any correct call for ${w} _{j}$, P must have already extracted ${\ell } _{{w} _{j}}$, and thus the predictor can extract ${\mathsf {prelab}} ({w} _{j})$ from ${\ell } _{{w} _{j}}$ and the call input without querying the oracle.

  • If ${w} _{j}\notin {\mathsf {P}} _{{i}}$ and the call is an inverse call, P can query the oracle and extract the information of ${\mathsf {prelab}} ({w} _{j})$ from the oracle answer.

  Given $w_{j}$ and ${\mathsf {prelab}} (w_{j})$, if ${{\mathbb {IP}}} = {{\mathbb {CF}}}$ or ${{\mathbb {IP}}} = {{\mathbb {IC}}}$, P can directly extract the label ${\ell } _{{v} _{j}}$ from ${\mathsf {prelab}} (w_{j})$ and ${b} _{j}$; if ${{\mathbb {IP}}} = {{\mathbb {RP}}}$ and ${v} _{j}$ is the only predecessor of $w_{j}$, P can extract ${\ell } _{{v} _{j}}={\mathsf {prelab}} (w_{j})$; if ${{\mathbb {IP}}} = {{\mathbb {RP}}}$ and $w_{j}$ has another predecessor u, we argue that ${\ell } _{u}$ was already known and thus the predictor can obtain the label ${\ell } _{{v} _{j}}={\mathsf {prelab}} (w_{j})\oplus {\ell } _{u}$.

  • If $u\notin {\mathsf {P}} _{{i}}$, since the ex-post-facto pebbling is legal and $w_{j} \in {\mathsf {P}} _{{\gamma }}$, there exists a round ${\gamma } '$ $(i< {\gamma } ' < r)$ such that $u\in {\mathsf {P}} _{{\gamma } '}\setminus {\mathsf {P}} _{{\gamma } '-1}$. By Claim 1, there is a correct call C(u) for u in round ${\gamma } '$. Then by Claim 2, P will recognize the call C(u) and update the label ${\ell } _u$.

  • If u is in ${\mathsf {P}} _{{i}}$ but the first critical call for u is before round ${\gamma }$ (but after round ${i}$), then ${\ell } _{u}$ was already known before round ${\gamma }$.

  • If u equals some node ${v} _{k}\in {\mathsf {P}} _{{i}}$ such that ${v} _{k}$ and ${v} _{j}$ have the same first critical call, since ${\ell } _{{v} _{j}}$ was unknown, it must be the case that $k < j$ and ${h} _{k} = {\ell } _{{v} _{k}}$, hence the predictors knew ${\ell } _{u}$ initially from the hint $H_{{i}}$.

• 2. Handling correct calls for ${\mathsf {P}} _{{i}}$: For each node ${v} _{j}\in {\mathsf {P}} _{{i}}$ and each correct ideal-primitive call for ${v} _{j}$ (note that by Claim 2, P correctly recognizes the call, as the $\ell$-labels of (first) critical calls upto round ${\gamma }$ were correctly extracted), since the predictor already knew ${\ell } _{{v} _{j}}$ after handling the first critical call for ${v} _{j}$,²¹ she can answer the call without querying the ideal primitive:

  • If ${{\mathbb {IP}}} ={{\mathbb {CF}}}$, then ${\ell } _{{v} _{j}}$ is the query answer.

  • If ${{\mathbb {IP}}} ={{\mathbb {IC}}}$ and the call input has the value $({k}, x)$ where ${k} \in \{0,1\}^{{L}}\cup \{\bot \}$ and $x\in \{0,1\}^{{L}}$, the answer is ${\ell } _{{v} _{j}}\oplus x$ because ${\ell } _{{v} _{j}}=x\oplus {{\mathsf {ip}}} ({k},x)$ for a forward call and ${\ell } _{{v} _{j}}=x\oplus {{\mathsf {ip}}} ^{-1}({k},x)$ for an inverse call.

  • If ${{\mathbb {IP}}} ={{\mathbb {RP}}}$ and the call input has the value x, the answer is ${\ell } _{{v} _{j}}\oplus x$ because ${\ell } _{{v} _{j}}=x\oplus {{\mathsf {ip}}} (x)$ for a forward call and ${\ell } _{{v} _{j}}=x\oplus {{\mathsf {ip}}} ^{-1}(x)$ for an inverse call.

For each round ${\gamma } > {i}$, after checking correct/critical calls for all nodes in ${\mathsf {P}} _{{i}}$, the predictor answers the other unanswered calls by making queries to the ideal primitive. Note that in round ${\gamma }$, for every node $v\in {\mathsf {P}} _{{i}}\cup \dots \cup {\mathsf {P}} _{{\gamma }}$, if there is a correct ideal-primitive call for v, since P already extracted $\ell$-labels for all (first) critical calls upto round ${\gamma }$, by Claim 2, P will recognize the call, get the call answer, then update the labels ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$, ${\ell } _{v}$ and the pre-labels of v’s successors.

After executing ${{\mathsf {A}}} ({\sigma } _{{i}})$, the predictor will compute ${\mathsf {prelab}} (v)$ for every $v\in {\mathbb {V}}$ according to topological order, and predict ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ for every $v\in {\mathsf {P}} _{{i}}$. In particular, if ${{\mathbb {IP}}} ={{\mathbb {CF}}}$, ${{\mathsf {ip}}} ({\mathsf {prelab}} (v)) = {\ell } _{v}$; if ${{\mathbb {IP}}} ={{\mathbb {IC}}}$, let x be the last ${L}$-bit string of ${\mathsf {prelab}} (v)$, then ${{\mathsf {ip}}} ({\mathsf {prelab}} (v)) = x \oplus {\ell } _{v}$; if ${{\mathbb {IP}}} ={{\mathbb {RP}}}$, then ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))={\mathsf {prelab}} (v)\oplus {\ell } _{v}$. Note that if $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ happens and the input is the hint h mentioned above, the predictor does not need to query ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ for any $v\in {\mathsf {P}} _{{i}}$ as the answer can be computed from ${\mathsf {prelab}} (v)$ and the extracted label ${\ell } _{v}$.

If $\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}}$ happens and P’s input is the hint mentioned above, the predictor will correctly predict $({\mathsf {prelab}} (v),{{\mathsf {ip}}} ({\mathsf {prelab}} (v)))$ for every $v\in {\mathsf {P}} _{{i}}$ without querying ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$. Recall that $\{{\mathsf {prelab}} (v)\}$ are distinct so that P also predicts $|{\mathsf {P}} _{{i}}|$ ideal-primitive entries.

First, we note that the labels being updated (including ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ for $v\in {\mathbb {V}}$) are correct by induction on the time order of updating. Initially, only the pre-labels of source vertices were updated which are correct. Assume all the labels being updated are correct up to now. A new label ${\mathsf {prelab}} (v)$ (or ${\mathsf {aftlab}} (v)$) will be updated because one of the following possibilities:

• 1. P recognizes the first correct call for $v\in {\mathsf {P}} _{{i}}$ from the hint $C_{{i}}$ (and thus correct by the hint).

• 2. P recognizes a correct call for v by finding out that the call input/output matches the previously updated ${\mathsf {aftlab}} (v)$ (or ${\mathsf {prelab}} (v)$) which is correct by inductive hypothesis.

• 3. P computes the label according to topological order (at the end).

• 4. ${\mathsf {prelab}} (v)$ is updated because the $\ell$-labels of v’s predecessors were all updated previously (which are correct by inductive hypothesis).

Similarly, a new label ${\ell } _{v}$ will be updated either because the possibility 2 as above, or because P extracts ${\ell } _{v}$ from the first critical call for v (and thus correct by the hint). Note that the argument above also implies that P will not output an incorrect prediction.

It remains to prove that P will never query ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ for any $v\in {\mathsf {P}} _{{i}}$. First, when simulating ${{{\mathsf {A}}} ({\sigma } _{{\sigma } _i})}$, P will recognize the first correct call of v from the hint $C_{{i}}$ and answer the call using the extracted label ${\ell } _{v}$. Then ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ will all be updated. For the following correct calls, since ${\mathsf {prelab}} (v)$, ${\mathsf {aftlab}} (v)$ and ${\ell } _{v}$ have been updated, P will recognize and answer the call without querying ${{\mathsf {ip}}}$. Lastly, when computing ${\mathsf {prelab}} (v)$ for $v\in {\mathbb {V}}$ according to topological order, P will not query ${{\mathsf {ip}}} ({\mathsf {prelab}} (v))$ for any $v\in {\mathsf {P}} _{{i}}$ as the answer will be computed from ${\mathsf {prelab}} (v)$ and the extracted label ${\ell } _{v}$.

In summary, with probability at least $\Pr [\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}} ]$, there exists a short hint h where P(h) correctly guesses $|{\mathsf {P}} _{{i}}|$ ideal-primitive entries, thus by Lemmas 9 and 10, we have $\Pr [\textsc {E}^{{\lambda },{{\mathbb {IP}}}}_{\mathsf {pred}} ] \le 2^{-{\lambda }}$ and the lemma holds.    $\square$

For an execution ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}},{r})$, we say ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}},{r})$ is correct if the algorithm generates the correct graph function output at the end; we say ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}},{r})$ is lucky if it is correct but there is a vertex $v\in {\mathsf {sink}}$ where ${{\mathsf {A}}}$ did not make any correct call for v before outputting the label ${\ell } _{v}$. Note that if ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}},{r})$ is correct but not lucky, the ex-post-facto pebbling will be successful. Moreover, with similar compression argument as in Lemmas 2 and 3, the probability (over the uniform choice of ${{\mathsf {ip}}}$ and ${{\mathsf {A}}}$’s internal coins) that ${{\mathsf {A}}}$ is lucky is no more than ${{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {IP}}})$, where ${{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {CF}}})=|{\mathbb {V}} |/2^{{L}}$ and ${{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {IC}}})={{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {RP}}})=|{\mathbb {V}} |/2^{{L}-1}$.

In summary, for any algorithm ${{\mathsf {A}}}$ that correctly computes the graph function with probability ${{\epsilon } _{{{\mathsf {A}}}}} >2\cdot ({{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})+ {{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {IP}}})+{{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {IP}}}))$, we set ${\lambda } \in {\mathbb {N}}$ as the minimal integer such that ${\epsilon } ({\lambda })={{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})+{{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {IP}}})+ {{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {IP}}})+2^{-{\lambda }}\le {{\epsilon } _{{{\mathsf {A}}}}}/2$. Then the following conditions hold with probability more than ${{\epsilon } _{{{\mathsf {A}}}}}-{\epsilon } ({\lambda })\ge {{\epsilon } _{{{\mathsf {A}}}}}/2$:

• 1. The pre-labels are distinct from each other.

• 2. The ex-post-facto pebbling is legal and successful, hence

  $$ \sum _{i=1}^{{t_{\mathsf {peb}}}} |{\mathsf {P}} _i| \ge {\mathsf {cc}} ({\mathbb {G}}). $$

• 3. For every ${i} \in [{t_{\mathsf {peb}}} ]$, it holds that $|{\sigma } _{{i}}|\ge |{\mathsf {P}} _{{i}}| \cdot {{\beta } _{{{\mathbb {IP}}}}}-{\lambda }.$ Here ${{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}};{r})$ terminates at round ${t_{\mathsf {peb}}} +1$, ${\sigma } _{{i}}$ is the input state for round ${i} +1$, and ${\mathsf {P}} _{{i}}$ is the pebbling configuration in round ${i}$. Thus we have

  $$\begin{aligned} {{\mathsf {CMC}}} ({{\mathsf {A}}} ^{{{\mathsf {ip}}}}({\mathbf {x}}; {r}))&\ge \sum _{{i} =1}^{{t_{\mathsf {peb}}}}|{\sigma } _{{i}}| \ge \sum _{i=1}^{{t_{\mathsf {peb}}}} (|{\mathsf {P}} _i|\cdot {{\beta } _{{{\mathbb {IP}}}}} - {\lambda }) \\&\ge \left( \sum _{i=1}^{{t_{\mathsf {peb}}}} |{\mathsf {P}} _i| \right) \cdot {{\beta } _{{{\mathbb {IP}}}}} - {t_{\mathsf {peb}}} \cdot {\lambda } \\&\ge {\mathsf {cc}} ({\mathbb {G}}) \cdot {{\beta } _{{{\mathbb {IP}}}}} - {t_{\mathsf {peb}}} \cdot {\lambda } \ge {\mathsf {cc}} ({\mathbb {G}}) \cdot {{\beta } _{{{\mathbb {IP}}},{\lambda }}}, \end{aligned}$$

  where ${{\beta } _{{{\mathbb {IP}}},{\lambda }}} = {{\beta } _{{{\mathbb {IP}}}}} - {\lambda }$ as ${\mathsf {cc}} ({\mathbb {G}})\ge {t_{\mathsf {peb}}}$.

Therefore we have

By plugging in the corresponding ${{\epsilon } _{{\mathsf {coll}}}} ({{\mathbb {IP}}})$, ${{\epsilon } _{{\mathsf {legal}}}} ({{\mathbb {IP}}})$, ${{\epsilon } _{{\mathsf {luck}}}} ({{\mathbb {IP}}})$ and ${{\beta } _{{{\mathbb {IP}}}}}$ for the ideal primitive ${{\mathbb {IP}}}$, we can find the optimal parameter ${\lambda } _{{{\mathbb {IP}}}}$, and compute

$$ {\beta } ({{\epsilon } _{{{\mathsf {A}}}}}, \log |{\mathbb {V}} |) = \frac{{{\epsilon } _{{{\mathsf {A}}}}}}{2} \cdot ({{\beta } _{{{\mathbb {IP}}}}} - {\lambda } _{{{\mathbb {IP}}}}), $$

which leads to Theorems 1, 2 and 3.

   $\square$

3.3 iMHFs from Small-Block Labeling Functions

In this section, from any graph, we construct graph-based iMHFs from the small-block labeling functions built in Sect. 3.1.

Proposition 1

Fix ${L} =2^{{\ell }}$ and let ${{\mathcal {H}}} _{{\mathsf {fix}}}$ be the ${\beta }$-small-block labeling function built in Sect. 3.1. For any 2-indegree (predecessors-distinct) DAG ${\mathbb {G}} = ({\mathbb {V}},{\mathbb {E}})$ with ${N} =2^{{n}}$ vertices and single source/sink, the graph labeling functions ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\mathsf {fix}}}}}$ is $({\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}},{\varDelta _{{{\mathcal {F}}}}},{N})$-memory hard, where for all ${\epsilon } \in [3\cdot 2^{-{L}/10},1]$, it holds that

$$ {\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}} ({\epsilon })\ge \varOmega ({\epsilon } \cdot {\mathsf {cc}} ({\mathbb {G}})\cdot {L}), \qquad \qquad {\varDelta _{{{\mathcal {F}}}}} ({\epsilon })\le O\left( \frac{{\mathsf {st}} ({\mathbb {G}},{N})}{{\mathsf {cc}} ({\mathbb {G}})}\right) . $$

Proof

The proof is deferred to full version.    $\square$

The graph ${\mathbb {G}}$ in [3] has pebbling complexities ${\mathsf {cc}} ({\mathbb {G}})=\varOmega ({N} ^2/{\text {log}}{N})$ and ${\mathsf {st}} ({\mathbb {G}},{N})=O({N} ^2/{\text {log}}{N})$, thus we obtain the following corollary.

Corollary 1

Fix ${L} =2^{{\ell }}$ and let ${{\mathcal {H}}} _{{\mathsf {fix}}}$ be the ${\beta }$-small-block labeling function built in Sect. 3.1. Let ${\mathbb {G}} = ({\mathbb {V}},{\mathbb {E}})$ be the 2-indegree (predecessors-distinct) DAG in [3] (with ${N} =2^{{n}}$ vertices). The graph labeling functions ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\mathsf {fix}}}}}$ is $({\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}},{\varDelta _{{{\mathcal {F}}}}},{N})$-memory hard, where for all ${\epsilon } \in [3\cdot 2^{-{L}/10},1]$, it holds that

$$ {\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}} ({\epsilon })\ge \varOmega \left( \frac{{\epsilon } \cdot {N} ^2\cdot {L}}{\log {N}}\right) , \qquad \qquad {\varDelta _{{{\mathcal {F}}}}} ({\epsilon })\le O(1). $$

4 MHFs from Wide-Block Labeling Functions

Ideally, we target a CMC which is as high as possible, while keeping the evaluation of the function within a feasible margin for the legitimate users. An option is to use a bigger graph with high CC and small-block labeling functions. However, this can lead to large description size. A way out here is to choose a graph family that has succinct description. Unfortunately, as far as we know, practical hard-to-pebble graphs are randomly sampled and do not have a succinct description of the actual graph, only of the sampling process. To reduce description complexity of MHFs, in this section, we construct a family of graph-based iMHFs based on an abstraction called wide-block labeling functions. In Sect. 4.1, we define and construct a family of wide-block labeling functions from small-block labeling functions. In Sect. 4.2, we prove that the construction satisfies pebbling reducibility with respect to depth-robust graphs. Finally in Sect. 4.3, we construct succinct iMHFs from wide-block labeling functions.

4.1 Wide-Block Labeling Functions: Definition and Construction

Definition 7

(Wide-Block Labeling Functions). For any ideal primitive ${{\mathbb {IP}}} ={{\mathbb {CF}}}/{{\mathbb {IC}}}/{{\mathbb {RP}}}$, ${\delta } \in {\mathbb {N}}$ and ${W} =2^{{w}}$, we say

$$ {{\mathcal {H}}} _{{\delta },{w}} = {\left\{ {\mathsf {vlab}^{{{\mathsf {ip}}}}_{{\gamma },{w}}}: {\{0,1\}} ^{{\gamma } {W}} \rightarrow {\{0,1\}} ^{{W}}\right\} } _{{{\mathsf {ip}}} \in {{\mathbb {IP}}},1\le {\gamma } \le {\delta }} $$

is a family of ${\beta } _{{\delta },{w}}$-wide-block labeling functions if it satisfies the following property.

• ${\beta } _{{\delta },{w}}$-pebbling reducibility w.r.t. depth-robust graphs: For any ${\epsilon } \in [0,1]$ and any ${\delta }$-indegree $({e}, {d})$-depth robust (first-predecessor-distinct) DAG ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$²², the graph functions ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta },{w}}}}$ satisfies

  $$ {{\mathsf {CMC}}} _{{\epsilon }}({{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta },{w}}}}) \ge {e} \cdot ({d}-1) \cdot {\beta } _{{\delta },{w}}({\epsilon }, \log |{\mathbb {V}} |), $$

  where ${{\mathsf {CMC}}} _{{\epsilon }}(\cdot )$ is ${\epsilon }$-cumulative-memory-complexity (Definition 1).

Next we show how to construct wide-block labeling functions from small-block labeling functions. The construction is the composition of two graph functions ${\mathsf {MIX}}$ and ${\mathsf {SSDR}}$, which can be built from any small-block labeling functions.

Fig. 1.

The graph ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ for ${K} =4$. We omitted the edges from ${\langle 0, j\rangle }$ to ${\langle 1, j\rangle }$ ($2\le j\le {K}$) for clarity of the figure.

Remark 5

There are tailored-made variable-length hash functions available in the real-world, for example within Scrypt [19, 20] and Argon2 [10]. However, even by modeling the underlying block/stream cipher as an ideal primitive, we do not know how to prove the pebbling-reducibility of the hash functions. Hence we seek another construction of labeling functions.

In the following context, we fix the indegree parameter ${\delta } \in {\mathbb {N}}$, ideal primitive length ${L} = 2^{{\ell }}$, output length ${W} = 2^{{w}}$ of the wide-block labeling functions, and denote as ${K} = 2^{{k}} \,{:=}\, {W}/{L}$ the ratio between ${W}$ and ${L}$. We will omit these variables in notation when it is clear in the context.

We show how to construct the family of labeling functions ${{\mathcal {H}}} _{{\delta },{w}}$. For any $1\le {\gamma } \le {\delta }$, and any ideal primitive ${{\mathsf {ip}}} \in {{\mathbb {IP}}}$, we define the labeling function ${\mathsf {vlab}^{{{\mathsf {ip}}}}_{{\gamma },{w}}}:{\{0,1\}} ^{{\gamma } {W}} \rightarrow {\{0,1\}} ^{{W}}$ as the composition of two functions, namely, ${{\mathsf {mix}} ^{{{\mathsf {ip}}}}_{{\gamma }}}:{\{0,1\}} ^{{\gamma } {W}} \rightarrow {\{0,1\}} ^{{W}}$ and ${{\mathsf {ssdr}} ^{{{\mathsf {ip}}}}_{{{\delta }}}}:{\{0,1\}} ^{{W}} \rightarrow {\{0,1\}} ^{{W}}$. More precisely, for an input vector $\mathbf {{x}}\in {\{0,1\}} ^{{\gamma } {W}}$, we define the ${W}$-bit function output as

$$ {\mathsf {vlab}^{{{\mathsf {ip}}}}_{{\gamma },{w}}} (\mathbf {{x}}) \,{:=}\, {{\mathsf {ssdr}} ^{{{\mathsf {ip}}}}_{{{\delta }}}} ({{\mathsf {mix}} ^{{{\mathsf {ip}}}}_{{\gamma }}} (\mathbf {{x}})). $$

Next, we specify the functions ${{\mathsf {mix}} ^{{{\mathsf {ip}}}}_{{\gamma }}}$ and ${{\mathsf {ssdr}} ^{{{\mathsf {ip}}}}_{{{\delta }}}}$.

Denote as ${\mathsf {flab}^{{{\mathsf {ip}}}}} : {\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}\rightarrow {\{0,1\}} ^{{L}}$ a small-block labeling function (Definition 6), and let ${K} \,{:=}\, {W}/{L}$ be the ratio between ${W}$ and ${L}$. We define

$$ {{\mathsf {mix}} ^{{{\mathsf {ip}}}}_{{\gamma }}} \,{:=}\, {{\mathsf {F}} ^{{{\mathsf {ip}}}}_{{{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}}}}: {\{0,1\}} ^{{\gamma } {W}} \rightarrow {\{0,1\}} ^{{W} ={K} {L}} $$

as the graph function (Sect. 2.3) built upon a DAG ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ and the labeling function ${\mathsf {flab}^{{{\mathsf {ip}}}}}$. (Note that we can use ${\mathsf {flab}^{{{\mathsf {ip}}}}}$ as the labeling function since the maximal indegree of ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ is 2.) The graph ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} = ({{\mathbb {V}} _{{\mathsf {mix}}}^{{\gamma },{K}}}, {{\mathbb {E}} _{{\mathsf {mix}}}^{{\gamma },{K}}})$ is defined as follows.

• Nodes set: The set ${{\mathbb {V}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ has ${\gamma } {K}$ source nodes (which represent the ${\gamma } {K}$ input blocks), and we use ${\langle 0, j\rangle }$ ($1\le j\le {\gamma } {K}$) to denote the jth source node. Besides, there are ${\gamma } {K}$ columns each with ${K}$ nodes. We use ${\langle i, j\rangle }$ ($1\le i \le {\gamma } {K}$, $1\le j\le {K}$) to denote the node at the ith column and jth row. The ${K}$ nodes at the last column are the sink nodes (which represent the ${K}$ output blocks).

• Edges set:The set ${{\mathbb {E}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ has ${\gamma } {K} ^2+{\gamma } ({K}-1) {K} +{K}-1$ edges. Each source node ${\langle 0, i\rangle }$ $(1\le i \le {\gamma } {K})$ has ${K}$ outgoing edges to the ${K}$ nodes of column i, namely, $\{{\langle i, j\rangle } \}_{j\in [{K} ]}$. For each column i ($1\le i < {\gamma } {K}$) and each row j ($1 \le j \le {K}$), the node ${\langle i, j\rangle }$ has an outgoing edge to ${\langle i+1, j\rangle }$ at the next column. Finally, each source node ${\langle 0, j\rangle }$ ($2 \le j \le {K}$) has an outgoing edge to ${\langle 1, j\rangle }$²³ (Fig. 1).

Denote as ${\mathsf {flab}^{{{\mathsf {ip}}}}} : {\{0,1\}} ^{{L}} \cup {\{0,1\}} ^{2{L}}\rightarrow {\{0,1\}} ^{{L}}$ a small-block labeling function (Definition 6), and let ${K} \,{:=}\, {W}/{L}$ be the ratio between ${W}$ and ${L}$. Fix ${{\delta }} \in {\mathbb {N}}$, we define

$$ {{\mathsf {ssdr}} ^{{{\mathsf {ip}}}}_{{{\delta }}}} \,{:=}\, {{\mathsf {F}} ^{{{\mathsf {ip}}}}_{{{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}}}: {\{0,1\}} ^{{W}} \rightarrow {\{0,1\}} ^{{W}} $$

as the graph function built upon the labeling function ${\mathsf {flab}^{{{\mathsf {ip}}}}}$ and a DAG ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$. (Note that we can use ${\mathsf {flab}^{{{\mathsf {ip}}}}}$ as the labeling function since the maximal indegree of ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ is 2.) ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} = ({{\mathbb {V}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}, {{\mathbb {E}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}})$ is a source-to-sink-depth-robust graph (Definition 4) defined as follows.

• Nodes set: The set ${{\mathbb {V}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ has ${K} (1+{{\delta }} {K})$ vertices distributing across $1+{{\delta }} {K}$ columns and ${K}$ rows. For every $i \in \{0,\dots ,{{\delta }} {K} \}$ and every $j \in \{1,\dots ,{K} \}$, we use ${\langle i, j\rangle }$ to denote the node at column i and row j. The ${K}$ nodes at column 0 are the source nodes and the ${K}$ nodes at column ${{\delta }} {K}$ are the sink nodes.

• Edges set: The set ${{\mathbb {E}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ consists of 3 types of edges. The first type is called horizontal edges: For every i ($0\le i < {{\delta }} {K}$) and every j ($1 \le j \le {K}$), there is an edge from node ${\langle i, j\rangle }$ to node ${\langle i+1, j\rangle }$. The second type is called vertical edges: For every i ($2\le i\le {{\delta }} {K}$) and every j ($1 \le j < {K}$), there is an edge from node ${\langle i, j\rangle }$ to node ${\langle i, j+1\rangle }$. The third type is called backward edges: For every j ($1 \le j < {K}$), there is an edge from node ${\langle {{\delta }} {K}, j\rangle }$ to node ${\langle 1, j+1\rangle }$. In total, there are ${{\delta }} {K} ^2+{{\delta }} {K} \cdot ({K}-1) < 2{{\delta }} {K} ^2$ edges (Fig. 2).

Fig. 2.

The graph ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ for ${K} =4$

We prove a useful lemma showing that ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ is source-to-sink-depth-robust.

Lemma 5

Fix any ${K} = 2^{{k}} \ge 4$ and ${\delta } \in {\mathbb {N}}$, the graph ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ is $(\frac{{K}}{4}, \frac{{\delta } {K} ^2}{2} )$-source-to-sink-depth-robust.

Proof

The proof is deferred to full version.    $\square$

4.2 Wide-Block Labeling Functions: Pebbling Reducibility

In this section, we show that the labeling functions constructed in Sect. 4.1 satisfy pebbling reducibility with respect to (first-predecessor-distinct) depth-robust graphs. We will make use of the following notation.

Given a graph ${\mathbb {G}} _{1}$ (with ${n} _{1}$ source nodes and ${n} _{2}$ sink nodes), and a graph ${\mathbb {G}} _{2}$ (with ${n} _{2}$ source nodes and ${n} _{3}$ sink nodes), we define ${\mathbb {G}} _{1}\circ {\mathbb {G}} _{2}$ as the composition of ${\mathbb {G}} _{1}$ and ${\mathbb {G}} _{2}$, namely, we merge the ith sink node of ${\mathbb {G}} _{1}$ with the ith source node of ${\mathbb {G}} _{2}$ for each $i\in [{n} _{2}]$²⁴, and take the union of the rest parts of the graphs.

Theorem 4

Fix ${L} = 2^{{\ell }}$, ${W} = 2^{{w}} \ge {L}$, and set ${K} \,{:=}\,{W}/{L}$. Let ${{\mathcal {H}}} _{{\mathsf {fix}}}$ be any ${\beta } _{{\mathsf {fix}}}$-small-block labeling functions. For any ${\delta } \in {\mathbb {N}}$, the labeling functions ${{\mathcal {H}}} _{{\delta },{w}}$ constructed in Sect. 4.1 is ${\beta } _ {{\delta },{w}}$-pebbling-reducible w.r.t. (first-predecessor-distinct²⁵) depth-robust graphs (with single source/sink) where

$$ {\beta } _{{\delta },{w}}({\epsilon },\log |{\mathbb {V}} |)\ge \frac{{\delta } {K} ^3}{8} \cdot {\beta } _{{\mathsf {fix}}}({\epsilon }, \log |{\mathbb {V}} |). $$

Here ${\epsilon } \in (0,1]$ and $|{\mathbb {V}} |$ is the number of vertices in the graph.

Remark 6

(Generalization). For the wide-block labeling functions constructed in Sect. 4.1, we make use of a specific graph ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ that is source-to-sink depth robust. We emphasize, however, that any source-to-sink depth robust graphs suffice. In particular, by replacing ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$ with any 2-indegree DAG ${{\mathbb {G}} ^{*}}$ where i) ${{\mathbb {G}} ^{*}}$ has ${K}$ source/sink nodes and ii) ${{\mathbb {G}} ^{*}}$ is $({e} ^{*}, {d} ^{*})$-source-to-sink depth robust, the corresponding wide-block labeling functions is still ${\beta }$-pebbling-reducible, where

$$ {\beta } ({\epsilon }, \log |{\mathbb {V}} |)\ge {e} ^{*} \cdot {d} ^{*} \cdot {\beta } _{{\mathsf {fix}}}({\epsilon }, \log |{\mathbb {V}} |). $$

We leave finding new source-to-sink depth-robust graphs as an interesting direction for future work.

Remark 7

Note that in Theorem 4, the pebbling reducibility only holds for depth-robust graphs. It is hard to directly link CMC and ${\mathsf {cc}} ({\mathbb {G}})$. More discussions can be found at Remark 2.

Proof

(of Theorem 4). Let ${\mathbb {G}} = ({\mathbb {V}}, {\mathbb {E}})$ be any (first-predecessor-distinct) $({e}, {d})$-depth-robust DAG with ${\delta }$-indegree and single source/sink, let ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta },{w}}}}$ be the graph functions built upon ${\mathbb {G}}$ and ${{\mathcal {H}}} _{{\delta },{w}}$. It is sufficient to show that for every ${\epsilon } \in (0,1]$,

$$ {{\mathsf {CMC}}} _{{\epsilon }}({{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta }, {w}}}}) \ge {\beta } _{{\mathsf {fix}}}({\epsilon }, \log |{\mathbb {V}} |) \cdot \frac{{\delta } {K} ^3}{8} \cdot {e} \cdot ({d}-1). $$

By opening the underlying graph structure of ${{\mathcal {H}}} _{{\delta },{w}}$, we see that ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta }, {w}}}}$ is also a graph function built upon functions ${{\mathcal {H}}} _{{\mathsf {fix}}}$ and an extension graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ that has the following properties.

• Nodes Expansion: Every node $v\in {\mathbb {V}}$ in the original graph ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ is expanded into ${K}$ nodes, that is,

  $$ {\mathsf {copy}} (v) \,{:=}\, \left( v^{(1)},\dots , v^{({K})}\right) . $$

• Neighborhood Connection: For every non-source node $v \in {\mathbb {V}} -{\mathsf {src}} ({\mathbb {G}})$, denote as ${\mathsf {pred}} (v) \,{:=}\, (u_1, \dots , u_{{\gamma }})$ the predecessors of v in ${\mathbb {G}}$. In ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$, there is a subgraph ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v) \circ {{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v)$ that connects

  $$ {\mathsf {neighbor}} (v) \,{:=}\, \{{\mathsf {copy}} (u_1), \dots , {\mathsf {copy}} (u_{{\gamma }}) \} $$

  to the set ${\mathsf {copy}} (v)$, where ${\mathsf {neighbor}} (v)$ (and ${\mathsf {copy}} (v)$) are the source nodes (and the sink nodes) of ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v) \circ {{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v)$, respectively. Note ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v) \circ {{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v)$ has the identical graph structure with the composition of ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}}$ and ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}}$.

By first-predecessor-distinctness of ${\mathbb {G}}$ and by the graph structure of the MIX graph, it holds that ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ is a predecessors-distinct graph with 2-indegree. Next, we will show that the extension graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ is $({e}, ({d}-1)\cdot {\delta } {K})$-depth-robust for ${K} \in \{1,2\}$ and $({e} {K}/4, ({d}-1)\cdot {\delta } {K} ^2/2)$-depth-robust for ${K} \ge 4$. By Lemma 1, for any ${K} = 2^{{k}} \ge 1$, we have

$$ {\mathsf {cc}} ({\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}) \ge \frac{{\delta } {K} ^3}{8} \cdot {e} \cdot ({d}-1). $$

Thus by ${\beta } _{{\mathsf {fix}}}$-pebbling reducibility of ${{\mathcal {H}}} _{{\mathsf {fix}}}$²⁶, we obtain Theorem 4.

Before proving the depth-robustness of the extension graph, we introduce a useful notation called meta-node [3]. Intuitively, meta-node maps each vertex of the original graph ${\mathbb {G}}$ to a set of vertices in ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$.

We define meta-node ${\mathsf {nodes}} (v)$ for every node $v\in {\mathbb {V}}$: For every non-source node $v \in {\mathbb {V}}- {\mathsf {src}} ({\mathbb {G}})$, we define ${\mathsf {nodes}} (v)$ as the set of vertices in the graph ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v)\circ {{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v)-{\mathsf {neighbor}} (v)$; for every source node $v\in {\mathsf {src}} ({\mathbb {G}})$, we define ${\mathsf {nodes}} (v)\,{:=}\,{\mathsf {copy}} (v)$. Note that for any $u,v\in {\mathbb {V}}$ such that $u\ne v$, the sets ${\mathsf {nodes}} (u)$ and ${\mathsf {nodes}} (v)$ are disjoint.

Next we show the depth robustness of the extension graph. We first consider the simpler case where ${K} \in \{1,2\}$. (In the following context, for a graph ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$, we sometimes think ${\mathbb {G}} ={\mathbb {V}} \cup {\mathbb {E}}$ as the union of set ${\mathbb {V}}$ and ${\mathbb {E}}$ if there is no ambiguity.)

Lemma 6

For any ${K} = 2^{{k}} \in \{1,2\}$ and $({e}, {d})$-depth robust DAG ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ that has maximal indegree ${\delta } \in {\mathbb {N}}$, the corresponding extension graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ is $({e}, ({d}-1)\cdot {\delta } {K})$-depth-robust.

Proof

The proof is deferred to full version.    $\square$

Next, we consider the more general case where ${K} \ge 4$.

Lemma 7

For any ${K} = 2^{{k}} \ge 4$ and any $({e}, {d})$-depth robust DAG ${\mathbb {G}} =({\mathbb {V}},{\mathbb {E}})$ with maximal indegree ${\delta } \in {\mathbb {N}}$, the corresponding extension graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ is $(\frac{{K}}{4}\cdot {e}, \frac{{\delta } {K} ^2}{2} \cdot ({d}-1))$-depth-robust.

Proof

For any nodes subset ${S_{\mathsf {ext}}} \subseteq {\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})}$ such that $|{S_{\mathsf {ext}}} | \le \frac{{K}}{4}\cdot {e}$, we show that ${\mathsf {depth}} ({\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})} -{S_{\mathsf {ext}}})\ge \frac{{\delta } {K} ^2}{2} \cdot ({d}-1)$, which finishes the proof.

From ${S_{\mathsf {ext}}}$, we first derive a set of nodes $S \subseteq {\mathbb {V}}$ in the graph ${\mathbb {G}}$, and find a long path in ${\mathbb {G}} -S$.

Claim 3

Define a set

$$ S \,{:=}\, {\left\{ v\in {\mathbb {V}}:|{\mathsf {nodes}} (v) \cap {S_{\mathsf {ext}}} | \ge \frac{{K}}{4}\right\} }, $$

there exists a ${d}$-path²⁷ ${P} = (v_1, \dots , v_{{d}})$ in the graph ${\mathbb {G}} -S$.

Proof

The proof is deferred to full version.    $\square$

Given the path ${P} = (v_1, \dots , v_{{d}}) \subseteq {\mathbb {G}} -S$, next in Lemma 8 we show that for every $i \in [{d}-1]$, there exists a long path from ${\mathsf {copy}} (v_i)$ to ${\mathsf {copy}} (v_{i+1})$ in the graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})} -{S_{\mathsf {ext}}}$, then by connecting the $d-1$ paths, we obtain a path with length at least $\frac{{\delta } {K} ^2}{2} \cdot ({d}-1)$, hence finish the proof of Lemma 7. Note that the path extraction from ${\mathsf {copy}} (v_i)$ to ${\mathsf {copy}} (v_{i+1})$ consists of two steps: First we exploit the structure of ${\mathsf {SSDR}}$ graphs and obtain a long path ending at a node in ${\mathsf {copy}} (v_{i+1})$, then we exploit the structure of ${\mathsf {MIX}}$ graphs and connect ${\mathsf {copy}} (v_{i})$ to the source node of the obtained path.

Lemma 8

Given the path ${P} = (v_1, \dots , v_{{d}}) \subseteq {\mathbb {G}} -S$ (obtained in Claim 3) and the graph ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})} -{S_{\mathsf {ext}}}$, there exists a nodes sequence $(u_{1}, \dots , u_{{d}})$ (where $u_{i}\in {\mathsf {copy}} (v_{i})-{S_{\mathsf {ext}}}$ for every $i\in [{d} ]$), such that for every $i\in [{d}-1]$, there is a path (with length at least $\frac{{\delta } {K} ^2}{2}$) that connects $u_{i}$ and $u_{i+1}$ in ${\mathsf {Ext}_{{\delta },{K}}({\mathbb {G}})} -{S_{\mathsf {ext}}}$.

Proof

We first show that there exists a path (with length at least $\frac{{\delta } {K} ^2}{2}$) from some node $u_1 \in {\mathsf {copy}} (v_1) -{S_{\mathsf {ext}}}$ to some node $u_2 \in {\mathsf {copy}} (v_2) -{S_{\mathsf {ext}}}$. (The arguments for $u_{2},\dots ,u_{{d}}$ will be similar.) The idea consists of two steps: First, we find a long source-to-sink path in ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2)$; second, we connect $u_1$ to the starting node of the source-to-sink path. We stress that the path we obtain has no intersection with ${S_{\mathsf {ext}}}$.

We first define a set ${S_{{\mathsf {ssdr}}}}$ and find a source-to-sink path in ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2)-{S_{{\mathsf {ssdr}}}}$.

Claim 4

Define ${\mathsf {row}} \subseteq [{K} ]$ as the set of row indices where j is in ${\mathsf {row}}$ if and only if the jth row of ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v_2)-{\mathsf {neighbor}} (v_2)$ has intersection with ${S_{\mathsf {ext}}}$. Define a set

$$ {S_{{\mathsf {ssdr}}}} \,{:=}\, {\left\{ {\langle 0, {j} \rangle } _{{\mathsf {ssdr}}}\right\} } _{{j} \in {\mathsf {row}}} \cup ( {S_{\mathsf {ext}}} \cap {{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2) ), $$

where ${\langle 0, {j} \rangle } _{{\mathsf {ssdr}}}$ is the source node of ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2)$ at row ${j}$. The graph ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2) -{S_{{\mathsf {ssdr}}}}$ has a source-to-sink path of ${{\mathbb {G}} _{{\mathsf {ssdr}}}^{{{\delta }},{K}}} (v_2)$ with length at least $\frac{{\delta } {K} ^2}{2}$.

Proof

The proof is deferred to full version.    $\square$

Next, we show how to connect ${\mathsf {copy}} (v_1) -{S_{\mathsf {ext}}}$ to the starting node of the source-to-sink path. Here we exploit the structure of MIX graphs.

Claim 5

Denote as $u_1$ an arbitrary node in the non-empty set²⁸ ${\mathsf {copy}} (v_1) -{S_{\mathsf {ext}}}$ and ${P_{\mathsf {{\mathsf {ssdr}}}}} (v_2)$ the source-to-sink path obtained in Claim 4. The graph ${{\mathbb {G}} _{{\mathsf {mix}}}^{{\gamma },{K}}} (v_2) -{S_{\mathsf {ext}}}$ has a path from $u_1$ to the starting node of ${P_{\mathsf {{\mathsf {ssdr}}}}} (v_2)$.

Proof

The proof is deferred to full version.    $\square$

Finally, using identical arguments, we can show that for every $i\in \{2,\dots ,{d}-1 \}$, there exists a path (with length at least $\frac{{\delta } {K} ^2}{2}$) from the node $u_i \in {\mathsf {copy}} (v_i) -{S_{\mathsf {ext}}}$ to some node $u_{i+1} \in {\mathsf {copy}} (v_{i+1}) -{S_{\mathsf {ext}}}$. Hence we finish the proof of Lemma 8.    $\square$

From Lemma 8, we obtain Lemma 7.    $\square$

From Lemmas 6 and 7, we obtain Theorem 4.    $\square$

4.3 iMHFs from Wide-Block Labeling Functions

In this section, from a relatively small depth-robust graph, we construct a graph-based iMHF with strong memory hardness based on the wide-block labeling functions built in Sect. 4.1.

Theorem 5

Fix ${L} =2^{{\ell }}$, ${W} =2^{{w}}$ and set ${K} \,{:=}\, {W}/{L}$. Let ${{\mathcal {H}}} _{{\delta },{w}}$ be the wide-block labeling functions built in Sect. 4.1. For any (first-predecessor-distinct²⁹) $({e},{d})$-depth-robust DAG ${\mathbb {G}} = ({\mathbb {V}},{\mathbb {E}})$³⁰ with ${\delta }$-indegree and ${N} =2^{{n}}$ vertices, the graph-based iMHFs family ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{{\delta },{w}}}}$ is $({\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}}, {\varDelta _{{{\mathcal {F}}}}},2{\delta } {N} {K} ^{2})$-memory hard, where for sufficiently large ${\epsilon } \le 1$, it holds that

$$ {\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}} ({\epsilon })\ge \varOmega ({\epsilon } \cdot {e} \cdot {d} \cdot {\delta } \cdot {K} ^2\cdot {W}), \qquad \qquad {\varDelta _{{{\mathcal {F}}}}} ({\epsilon })\le O\left( \frac{{\mathsf {st}} ({\mathbb {G}},{N})}{{e} \cdot {d}}\right) . $$

The graph ${\mathbb {G}}$ in [3] is $(\varOmega ({N}/{\text {log}}{N}), \varOmega ({N}))$-depth-robust and satisfies ${\mathsf {st}} ({\mathbb {G}},{N})=O({N} ^2/{\text {log}}{N})$, thus we obtain the following corollary.

Corollary 2

Fix ${L} =2^{{\ell }}$, ${W} =2^{{w}}$ and set ${K} \,{:=}\, {W}/{L}$. Let ${{\mathcal {H}}} _{2,{w}}$ be the labeling functions built in Sect. 4.1 and ${\mathbb {G}} = ({\mathbb {V}},{\mathbb {E}})$ be the 2-indegree DAG in [3] (with ${N} =2^{{n}}$ vertices). The graph labeling functions ${{\mathcal {F}} _{{\mathbb {G}},{{\mathcal {H}}} _{2,{w}}}}$ is $({\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}},{\varDelta _{{{\mathcal {F}}}}}, O({N} {K} ^{2}))$-memory hard, where for sufficiently large ${\epsilon } \le 1$, it holds that

$$ {\mathsf {C}^{\Vert }_{{{\mathcal {F}}}}} ({\epsilon })\ge \varOmega \left( \frac{{\epsilon } \cdot {N} ^2\cdot {K} ^2\cdot {W}}{ \log {N}}\right) , \qquad \qquad {\varDelta _{{{\mathcal {F}}}}} ({\epsilon })\le O(1). $$

Proof

(of Theorem 5). The proof is deferred to full version.    $\square$

5 Instantiations and Open Problems

We defer instantiations and discussions of future work in full version.

A Compression Arguments

Lemma 9

([16]). Fix an algorithm ${{\mathsf {A}}}$, let ${\mathcal {B}}$ be a sequence of random bits. ${{\mathsf {A}}}$ on input a hint ${h} \in {\mathcal {H}}$ adaptively queries specific bits of ${\mathcal {B}}$ and outputs ${p}$ indices of ${\mathcal {B}}$ that were not queried before, along with guesses for each of the bits. The probability (over the choice of ${\mathcal {B}}$ and randomness of ${{\mathsf {A}}}$) that there exists an ${h} \in {\mathcal {H}}$ where ${{\mathsf {A}}} ({h})$ guesses all bits correctly is at most $|{\mathcal {H}} |/2^{{p}}$.

Lemma 10

Fix ${L} \in {\mathbb {N}}$ and an algorithm ${{\mathsf {A}}}$ that can make no more than ${{\mathsf {q}}} =2^{{L}-2}$ oracle queries. Let ${{\mathsf {ic}}}$ be an ideal cipher uniformly chosen from the set ${{\mathbb {IC}}}$ with domain ${\mathcal {K}} \times {\{0,1\}} ^{{L}}$ and image ${\{0,1\}} ^{{L}}$.³¹ ${{\mathsf {A}}}$ on input a hint ${h} \in {\mathcal {H}}$ adaptively makes forward/inverse queries to ${{\mathsf {ic}}}$, and outputs ${p} \le 2^{{L}-2}$ ideal primitive entries (as well as guesses for each of the entry values) that were not queried before. The probability (over the choice of ${{\mathsf {ic}}}$ and randomness of ${{\mathsf {A}}}$) that there exists an ${h} \in {\mathcal {H}}$ where ${{\mathsf {A}}} ({h})$ guesses all permutation entries correctly is at most $|{\mathcal {H}} |/2^{{p} ({L}-1)}$.

Proof

The proof is deferred to full version.    $\square$