Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Cryptanalysis, Hash Functions, Bandwidth-Hard Functions, MHFs, Argon2i, scrypt, Red-blue pebbling

Original Publication (with major differences): Proceedings of the 25th ACM Conference on Computer Security (CCS 2018)

Date: received 23 Feb 2018, last revised 30 Sep 2018

Contact author: samsonzhou at gmail com

Available format(s): PDF | BibTeX Citation

Note: Full version of CCS 2018 paper.

Version: 20181001:005429 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]