Blocki, Jeremiah ;
Lee, Seunghoon ;
Zhou, Samson
Approximating Cumulative Pebbling Cost Is Unique Games Hard
Abstract
The cumulative pebbling complexity of a directed acyclic graph G is defined as cc(G) = min_P ∑_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, cc(G) captures the amortized SpaceTime 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 cc(G) is tightly related to the amortized AreaTime complexity of the DataIndependent MemoryHard Function (iMHF) f_{G,H} [Joël Alwen and Vladimir Serbinenko, 2015] defined using a constant indegree directed acyclic graph (DAG) G and a random oracle H(⋅). A secure iMHF should have amortized SpaceTime complexity as high as possible, e.g., to deter bruteforce 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 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 NPHard to compute cc(G), but their techniques do not even rule out an efficient (1+ε)approximation algorithm for any constant ε>0. We show that for any constant c > 0, it is Unique Games hard to approximate 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,ε >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 ε)}/k and d_1=k N^{2 ε/(1+2 ε)}, and the case that G is (e_2, d_2)depthrobust with e_2 = (1ε)k e_1 and d_2= 0.9 N^{(1+ε)/(1+2 ε)}, which may be of independent interest. Our result generalizes a result of Svensson who proved an analogous result for DAGs with indegree 𝒪(N).
BibTeX  Entry
@InProceedings{blocki_et_al:LIPIcs:2020:11698,
author = {Jeremiah Blocki and Seunghoon Lee and Samson Zhou},
title = {{Approximating Cumulative Pebbling Cost Is Unique Games Hard}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {13:113:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11698},
URN = {urn:nbn:de:0030drops116983},
doi = {10.4230/LIPIcs.ITCS.2020.13},
annote = {Keywords: Cumulative Pebbling Cost, Approximation Algorithm, Unique Games Conjecture, ?Extreme Depth Robust Graph, Superconcentrator, MemoryHard Function}
}
06.01.2020
Keywords: 

Cumulative Pebbling Cost, Approximation Algorithm, Unique Games Conjecture, γExtreme Depth Robust Graph, Superconcentrator, MemoryHard Function 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 