On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling

Jeremiah Blocki, Samson ZhouFinancial Cryptography 2016 · OpenReview

TL;DR

This paper investigates the computational complexity of finding the minimum cumulative cost for a "black pebbling" strategy on directed acyclic graphs (DAGs). This problem is crucial for analyzing the security of memory-hard functions used in password hashing. The authors prove that this problem is NP-Hard and that its linear programming relaxation has a large integrality gap, suggesting that efficient approximation algorithms are unlikely to exist.

What Problem Does This Paper Address?

Password hashing algorithms often rely on memory-hard functions (MHFs) to make them resistant to brute-force attacks, even with specialized hardware. Data-independent MHFs, a type of MHF, are modeled using directed acyclic graphs (DAGs), where nodes represent computations and edges represent data dependencies. The "pebbling game" on these DAGs is a model for how these functions are computed. Specifically, the cumulative cost of a pebbling strategy represents the total memory usage over time, which is a key metric for analyzing the amortized cost of an adversary trying to crack passwords by evaluating the hash function on many different inputs.

The problem addressed here is finding a "black pebbling" strategy for a DAG that minimizes this cumulative cost. While previous work focused on space-time cost, this paper argues that cumulative cost is a more relevant metric for analyzing the security of MHFs against parallel or amortized attacks. The authors aim to understand the computational difficulty of finding this optimal pebbling strategy and whether efficient algorithms can approximate it.

Methods

The paper's core contributions lie in establishing the computational complexity of the minimal cumulative cost graph pebbling problem. The authors employ several key techniques:

  • NP-Completeness Proof: They prove that the decision problem "Is the minimum cumulative cost of pebbling DAG G less than or equal to k?" is NP-Complete. This is achieved by first showing that a related problem, "Bounded 2-Linear Covering" (B2LC), is NP-Complete. Then, they construct a novel DAG based on a B2LC instance such that its optimal pebbling cost directly corresponds to the satisfiability of the B2LC instance. This reduction is a significant technical contribution, requiring the design of specialized "gadgets" (variable, equation, and assignment gadgets) to bridge the gap between the two problems.
  • Integrality Gap Analysis: They analyze the linear programming (LP) relaxation of the integer program formulation for cumulative cost pebbling. They demonstrate that this LP relaxation has a large integrality gap, meaning the optimal solution to the LP can be significantly larger than the optimal integer solution. This suggests that standard LP-based approximation algorithms are unlikely to perform well.
  • Hardness of Approximation: Based on the large integrality gap and related results on depth-reducible graphs, the authors conjecture that the problem is hard to approximate within constant factors.
  • NP-Hardness of Depth-Reducibility: They also show that determining if a DAG is "(e, d)-reducible" (meaning a subset of size 'e' can be removed to make all paths shorter than 'd') is NP-Complete. This is relevant because depth-robustness (the opposite of reducibility) is a necessary condition for secure MHFs.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and uses constructed DAGs for proofs rather than real-world datasets.

Key Insights and Ideas

  • Cumulative Cost is Fundamentally Hard: The paper establishes that minimizing cumulative cost for graph pebbling is computationally hard (NP-Complete). This is a significant result because it implies that finding optimal strategies for memory-hard functions is likely intractable for large graphs.
  • LP Relaxation is Weak: The large integrality gap for the LP relaxation is a crucial finding. It means that simply solving the relaxed version of the problem won't give a good approximation of the true minimum cost, forcing a search for more powerful algorithmic techniques if approximation is desired.
  • Depth-Robustness is Related but Distinct: The NP-completeness of testing for (e, d)-reducibility highlights a related but distinct hardness result. While depth-robustness is important for MHFs, its hardness doesn't directly imply the hardness of cumulative cost pebbling, necessitating specific reductions.
  • Gadget Design is Key: The construction of specialized graph gadgets (variable, equation, assignment) for the B2LC to minCC reduction is a novel and intricate part of the paper, showcasing a sophisticated approach to proving NP-completeness.

Key Results

  • NP-Completeness of minCC: The decision problem for minimal cumulative cost graph pebbling (minCC) is proven to be NP-Complete, even for DAGs with constant indegree.
  • Large Integrality Gap: The LP relaxation of the integer program for cumulative cost pebbling has an integrality gap of $\tilde{\Omega}(n)$, where $n$ is the number of nodes.
  • NP-Completeness of REDUCIBLEd: The problem of determining if a DAG is (e, d)-reducible is NP-Complete for $d > 0$.
  • Hardness of Approximation for REDUCIBLEd: It is NP-Hard to 1.3-approximate the minimum size vertex set for depth reduction, and under the Unique Games Conjecture, it's hard to (2-$\epsilon$)-approximate.

Limitations and Future Work

  • Approximation Algorithms: While the paper provides strong evidence against efficient approximation algorithms for cumulative cost pebbling (due to NP-hardness and large integrality gaps), it doesn't definitively rule out the existence of some approximation algorithm. The authors leave open the question of whether efficient approximation algorithms for minREDUCIBLEd exist.
  • Practical Implications: The paper's results suggest that automating the cryptanalysis of memory-hard functions using pebbling strategies might be difficult in the general case. Future work could focus on developing algorithms for specific classes of DAGs or exploring alternative metrics if cumulative cost proves too challenging.
  • Gap Between Upper and Lower Bounds: The paper notes that for some practical iMHF candidates, there's a large gap between known upper and lower bounds on their cumulative pebbling cost. Bridging this gap remains an open challenge.
  • Constant Factors: The paper focuses on asymptotic complexity. Understanding the actual constant factors in the hardness results and bounds would be crucial for practical security analysis.

Summary updated

Abstract

We consider the computational complexity of finding a legal black pebbling of a DAG $G=(V,E)$ with minimum cumulative cost. A black pebbling is a sequence $P_0,\ldots, P_t \subseteq V$ of sets of nodes which must satisfy the following properties: $P_0 = \emptyset$ (we start off with no pebbles on $G$), $\mathsf{sinks}(G) \subseteq \bigcup_{j \leq t} P_j$ (every sink node was pebbled at some point) and $\mathsf{parents}\big(P_{i+1}\backslash P_i\big) \subseteq P_i$ (we can only place a new pebble on a node $v$ if all of $v$'s parents had a pebble during the last round). The cumulative cost of a pebbling $P_0,P_1,\ldots, P_t \subseteq V$ is $\mathsf{cc}(P) = | P_1| + \ldots + | P_t|$. The cumulative pebbling cost is an especially important security metric for data-independent memory hard functions, an important primitive for password hashing. Thus, an efficient (approximation) algorithm would be an invaluable tool for the cryptanalysis of password hash functions as it would provide an automated tool to establish tight bounds on the amortized space-time cost of computing the function. We show that such a tool is unlikely to exist. In particular, we prove the following results. (1) It is $\texttt{NP}\mbox{-}\texttt{Hard}$ to find a pebbling minimizing cumulative cost. (2) The natural linear program relaxation for the problem has integrality gap $\tilde{O}(n)$, where $n$ is the number of nodes in $G$. We conjecture that the problem is hard to approximate. (3) We show that a related problem, find the minimum size subset $S\subseteq V$ such that $\textsf{depth}(G-S) \leq d$, is also $\texttt{NP}\mbox{-}\texttt{Hard}$. In fact, under the unique games conjecture there is no $(2-\epsilon)$-approximation algorithm.
BibTeX
@inproceedings{blocki2016computational,
  author = {Jeremiah Blocki and Samson Zhou},
  title = {{On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling}},
  booktitle = {Financial Cryptography},
  year = {2016},
  url = {https://openreview.net/forum?id=pfnAeGG82O-},
}
Figure