---
res:
bibo_abstract:
- "Memory-hard functions (MHF) are functions whose evaluation cost is dominated
by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated
hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware
(like x86 CPUs). MHFs have interesting cryptographic applications, most notably
to password hashing and securing blockchains.\r\n\r\nAlwen and Serbinenko [STOC’15]
define the cumulative memory complexity (cmc) of a function as the sum (over all
time-steps) of the amount of memory required to compute the function. They advocate
that a good MHF must have high cmc. Unlike previous notions, cmc takes into account
that dedicated hardware might exploit amortization and parallelism. Still, cmc
has been critizised as insufficient, as it fails to capture possible time-memory
trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc
could still have very different actual hardware cost.\r\n\r\nIn this work we address
this problem, and introduce the notion of sustained-memory complexity, which requires
that any algorithm evaluating the function must use a large amount of memory for
many steps. We construct functions (in the parallel random oracle model) whose
sustained-memory complexity is almost optimal: our function can be evaluated using
n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input
length) random oracle, while any algorithm that can make arbitrary many parallel
queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.\r\n\r\nAs
has been done for various notions (including cmc) before, we reduce the task of
constructing an MHFs with high sustained-memory complexity to proving pebbling
lower bounds on DAGs. Our main technical contribution is the construction is a
family of DAGs on n nodes with constant indegree with high “sustained-space complexity”,
meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles
for at least Ω(n) steps.\r\n\r\nAlong the way we construct a family of maximally
“depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction
of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joel F
foaf_name: Alwen, Joel F
foaf_surname: Alwen
foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Jeremiah
foaf_name: Blocki, Jeremiah
foaf_surname: Blocki
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
bibo_doi: 10.1007/978-3-319-78375-8_4
bibo_volume: 10821
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Sustained space complexity@
...