Crypto Reading Group

High Parallel Complexity Graphs and Memory-Hard Functions

Recently, we have witnessed the growing use of GPUs, FPGAs and even application-specific integrated circuits (ASICs) as the computational devices of choice used to mount very cost-effective brute-force evaluation of certain security relevant functions. Notable examples are brute-forcing of password hashes and the continuous solving of the proofs-of-work required to mine various cryptocurrencies.

In light of this development and the large cost of high-speed memory components for ASICs, FPGAs and GPUs we introduce the notion of parallel memory-hard functions. These come equipped with a "hardness parameter" n such that:
1. For any set of inputs, the required amount of memory x time, amortized per evaluation, even when using an arbitrarily parallel computational device, is roughly proportional to n^2.
2. Yet, to compute the function even on any single input using a sequential computational device no more memory x time is required.

Next we turn to constructing a parallel memory-hard function in the Random Oracle Model. As a key tool we use a new and very intuitive parallel pebbling game over directed acyclic graphs (DAGs) modeling input-independent parallel computation. In particular, first we introduce a new complexity notion, called "cumulative complexity (CC)", for DAGs in terms of this pebbling game. Next, given a DAG G, we describe a mapping to a function f_G in the ROM. Finally, we show a lower-bound on the parallel memory-hardness of f_G in terms of the CC of G.

This reduces the problem of building memory-hard functions to finding a family of DAGs with increasingly large CC. A simple observation shows that (even for a sequential pebbling game) any DAG with N nodes can have CC no greater than O(N^2). We build a family of constant in-degree graphs (one per possible size) such that the graph of size N has CC of at least \tilde{\Omega}(N^2). That is, each graphs has optimally high CC, within a polylogarithmic factor, for any graph of equal size.