You are looking at a specific version 20180407:060041 of this paper. See the latest version.

Paper 2018/221

Bandwidth-Hard Functions: Reductions and Lower Bounds

Jeremiah Blocki and Ling Ren and Samson Zhou

Abstract

Memory Hard Functions (MHFs) have been proposed as an answer to the growing inequality between the computational speed of general purpose CPUs and Application Specific Integrated Circuits (ASICs). MHFs have seen widespread applications including password hashing, key stretching and proofs of work. Several metrics have been proposed to quantify the `memory hardness' of a function. Cumulative memory complexity (CMC) (Alwen and Serbinenko, STOC 2015) (or amortized Area $\times$ Time complexity (Alwen et. al., CCS 2017)) attempts to quantify the amortized cost to acquire/build the hardware to evaluate the function --- amortized by the number of instances of the function that can be evaluated of this hardware. By contrast, bandwidth hardness (Ren and Devadas, TCC 2017) attempts to quantify the amortized energy costs of evaluating this function on hardware --- which in turn is largely dominated by the number of cache misses. Ideally, a good MHF would be both bandwidth hard and have high cumulative memory complexity. While the cumulative memory complexity of leading MHF candidates is well understood, little is known about the bandwidth hardness of many of the most prominent MHF candidates. Our contributions are as follows: First, we provide the first reduction proving that, in the parallel random oracle model, the bandwidth hardness of a Data-Independent Memory Hard Function (iMHF) is described by the red-blue pebbling cost of the directed acyclic graph (DAG) associated with that iMHF. Second, we show that the goals of designing an MHF with high CMC/bandwidth hardness are well aligned. In particular, we prove that any function with high CMC also has relatively high bandwidth costs. This result leads to the first unconditional lower bound on the bandwidth cost of scrypt. Third, we analyze the bandwidth hardness of several prominent iMHF candidates such as Argon2i (Biryukov et. al., 2015), winner of the password hashing competition, aATSample and DRSample (Alwen et. al., CCS 2017) --- the first practical iMHF with asymptotically optimal CMC. More specifically, we show that Argon2i is maximally bandwidth hard as long as the cache-size $m$ is at most $m \in O(n^{2/3-\epsilon})$ where $n$ is the total number of data-labels produced during computation. We also show that aATSample and DRSample are maximally bandwidth hard as long as the cache-size is $m \in O(n^{1-\epsilon})$. Finally, we show that the problem of finding a red-blue pebbling with minimum bandwidth cost is NP-hard.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisHash FunctionsBandwidth-Hard FunctionsMHFsArgon2iscryptRed-blue pebbling
Contact author(s)
samsonzhou @ gmail com
History
2024-02-07: last of 8 revisions
2018-02-27: received
See all versions
Short URL
https://ia.cr/2018/221
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.