Approximating Cumulative Pebbling Cost is Unique Games Hard

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

Abstract

The cumulative pebbling complexity of a directed acyclic graph (DAG) $G$, denoted as $\mathsf{cc}(G)$, is defined as the minimum total number of pebbles used over all rounds of a legal parallel black pebbling of $G$. This metric is critical in cryptography because it represents the amortized space-time complexity of Data-Independent Memory-Hard Functions (iMHFs). While previous work established that computing $\mathsf{cc}(G)$ exactly is $\mathsf{NP}$-Hard, the feasibility of efficient approximation remained an open question. This paper demonstrates that for any constant $c > 0$, it is Unique Games hard to approximate $\mathsf{cc}(G)$ within a factor of $c$, even for graphs with constant indegree.

Introduction

Memory-Hard Functions (MHFs) are cryptographic primitives designed to be computationally expensive in terms of both time and memory. Their primary application is in password hashing (e.g., Argon2i), where they serve to increase the cost of brute-force attacks by requiring significant hardware resources. The security of an iMHF is typically analyzed using the parallel black pebbling game on a DAG $G$, where nodes represent intermediate values and pebbles represent stored data.

The cumulative pebbling cost $\mathsf{cc}(G)$ is the standard metric for evaluating the "memory-hardness" of these functions. A secure iMHF should have a high $\mathsf{cc}(G)$ to ensure that any attacker must incur high costs. However, evaluating candidate iMHFs is difficult because upper and lower bounds for leading designs often differ by orders of magnitude. This research addresses whether we can develop algorithms to efficiently approximate $\mathsf{cc}(G)$, providing a definitive negative answer under the Unique Games Conjecture.

The Complexity of Pebbling

In the parallel black pebbling game, a pebble can be placed on a node only if all its predecessors already have pebbles. The goal is to pebble all output nodes while minimizing the sum of pebbles present across all time steps. This sum, the cumulative cost, captures the amortized Area-Time complexity of computing the function on specialized hardware like ASICs.

Prior to this work, it was known that computing $\mathsf{cc}(G)$ exactly is $\mathsf{NP}$-Hard. However, this did not rule out the existence of a $(1+\varepsilon)$-approximation algorithm. If such an algorithm existed, designers could use it to verify the security of new iMHF candidates. This paper proves that such an approximation is likely impossible, showing that the problem is hard to approximate within any constant factor $c$.

Technical Methodology

The authors establish their result through a reduction from the Unique Games problem. The reduction involves three primary technical components:

1. Svensson’s Construction and Indegree Constraints

The proof builds on Svensson’s reduction from Unique Games to the DAG Vertex Deletion problem. A significant challenge was that Svensson's original construction resulted in graphs with an indegree proportional to the number of nodes $N$. In contrast, cryptographic hash functions are built on graphs with very small, constant indegrees (typically 2 or 3). The authors had to bridge this gap to make the hardness result relevant to real-world cryptography.

2. $\gamma$-Extreme Depth-Robust Graphs

To maintain hardness while reducing the indegree, the authors utilized "extreme" depth-robust graphs. A graph is depth-robust if it contains a long path even after a significant fraction of its nodes are deleted. By integrating these graphs into the reduction, the authors ensured that the resulting DAGs maintained the necessary structural complexity even with a constant number of edges per node.

3. Superconcentrator Overlays

To create a clear "gap" in pebbling cost between satisfiable and unsatisfiable Unique Games instances, the authors employed superconcentrator overlays. Superconcentrators are sparse graphs with high connectivity properties. By overlaying these onto the construction, they acted as cost amplifiers. This ensured that if the original Unique Games instance was "hard," the cumulative pebbling cost would be massive, whereas if it was "easy," the cost would remain relatively low, thereby establishing the hardness of approximation.

Key Results and Implications

  • Hardness of $\mathsf{cc}(G)$: The main theorem states that for any constant $c > 0$, approximating $\mathsf{cc}(G)$ for a constant-indegree DAG is Unique Games hard.
  • DAG Vertex Deletion: The paper proves that the DAG Vertex Deletion problem—finding the minimum set of nodes to remove to reduce a graph's depth—is also Unique Games hard to approximate on constant-indegree graphs. This is a significant result for the broader field of theoretical computer science.
  • Security Verification: The findings suggest that we cannot rely on automated tools to provide tight estimates of the memory-hardness of iMHF candidates. Security analysis must continue to rely on manual proofs and specific structural properties like depth-robustness.

Conclusion

This work provides a strong theoretical limit on our ability to analyze the security of memory-hard functions. By proving that approximating cumulative pebbling cost is Unique Games hard, the authors highlight the inherent difficulty in measuring the resistance of iMHFs to hardware-based attacks. Future research may explore whether these hardness results extend to non-constant approximation factors or if average-case instances of the problem remain tractable for practical purposes.

Summary updated

Abstract

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 any constant $c > 0$, it is Unique Games hard to approximate $\mathsf{cc}(G)$ to within a factor of $c$. (See the paper for the full abstract.)
BibTeX
@inproceedings{blocki2020approximating,
  author = {Jeremiah Blocki and Seunghoon Lee and Samson Zhou},
  title = {{Approximating Cumulative Pebbling Cost is Unique Games Hard}},
  booktitle = {ITCS},
  year = {2020},
  url = {https://openreview.net/forum?id=PPnKbhykMYH},
}
Figure