On the computational complexity of minimal cumulative cost graph pebbling

DOI10.1007/978-3-662-58387-6_18MaRDI QIDQ2656946zbMATH OpenOpenAlexFDO

Authors Jeremiah Blocki, Samson Zhou

Publication date 17 March 2021

Full work available at URL https://arxiv.org/abs/1609.04449

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer security (68M25)

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}subseteqV$ of sets of nodes which must satisfy the following properties: $P_0=emptyset$ (we start off with no pebbles on $G$), $$ (every sink node was pebbled at some point) and $$ (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}subseteqV$ is $mathsfcc(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 $extttNPmbox-extttHard$ to find a pebbling minimizing cumulative cost. (2) The natural linear program relaxation for the problem has integrality gap $ildeO(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 $SsubseteqV$ such that $extsfdepth(G-S)leqd$, is also $extttNPmbox-extttHard$. In fact, under the unique games conjecture there is no $(2-epsilon)$-approximation algorithm.

Recommendations

• Depth-robust graphs and their cumulative memory complexity
• On the depth-robustness and cumulative pebbling cost of Argon2i
• The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
• Sustained space complexity
• Data-independent memory hard functions: new attacks and stronger constructions

Cited in

(5)

• On properties of pebble assignment graphs
• On the depth-robustness and cumulative pebbling cost of Argon2i
• The Complexity of Graph Pebbling
• Cycles and girth in pebble assignment graphs
• Static-memory-hard functions, and modeling the cost of space vs. time

This page was built for publication: On the computational complexity of minimal cumulative cost graph pebbling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656946)