ITCS 2020: Approximating Cumulative Pebbling Cost is Unique Games Hard

Jeremiah Blocki1, Seunghoon Lee1, and Samson Zhou2

1Department of Computer Science, Purdue University
2School of Computer Science, Carnegie Mellon University


The cumulative pebbling complexity of a directed acyclic graph $G$ is defined as \[\mathsf{cc}(G) = \min_P \sum_i |P_i|,\] where the minimum is taken over all legal (parallel) black pebblings of \(G\) and \(|P_i|\) denotes the number of pebbles on the graph during round \(i\). Intuitively, \(\mathsf{cc}(G)\) captures the amortized Space-Time complexity of pebbling \(m\) copies of \(G\) in parallel. The cumulative pebbling complexity of a graph \(G\) is of particular interest in the field of cryptography as \(\mathsf{cc}(G)\) is tightly related to the amortized Area-Time complexity of the Data-Independent Memory-Hard Function (iMHF) \(f_{G,H}\) [AS15] defined using a constant indegree directed acyclic graph (DAG) \(G\) and a random oracle \(H(\cdot)\). A secure iMHF should have amortized Space-Time complexity as high as possible, e.g., to deter brute-force password attacker who wants to find \(x\) such that \(f_{G,H}(x) = h\). Thus, to analyze the (in)security of a candidate iMHF \(f_{G,H}\), it is crucial to estimate the value \(\mathsf{cc}(G)\) but currently, upper and lower bounds for leading iMHF candidates differ by several orders of magnitude. Blocki and Zhou recently showed that it is \(\mathsf{NP}\)-Hard to compute \(\mathsf{cc}(G)\), but their techniques do not even rule out an efficient \((1+\varepsilon)\)-approximation algorithm for any constant \(\varepsilon>0\). We show that for \(\mathit{any}\,\) constant \(c > 1\), it is Unique Games hard to approximate \(\mathsf{cc}(G)\) to within a factor of \(c\).

Along the way, we show the hardness of approximation of the DAG Vertex Deletion problem on DAGs of constant indegree. Namely, we show that for any \(k,\varepsilon >0\) and given a DAG \(G\) with \(N\) nodes and constant indegree, it is Unique Games hard to distinguish between the case that \(G\) is \((e_1, d_1)\)-reducible with \(e_1=N^{1/(1+2\varepsilon)}/k\) and \(d_1=k N^{2\varepsilon/(1+2\varepsilon)}\), and the case that \(G\) is \((e_2, d_2)\)-depth-robust with \(e_2 = (1-\varepsilon)k e_1\) and \(d_2= 0.9 N^{(1+\varepsilon)/(1+2\varepsilon)}\), which may be of independent interest. Our result generalizes a result of Svensson who proved an analogous result for DAGs with indegree \(\mathcal{O}(N)\).

Further Materials.


Contact Information.