Joël Alwen: Memory-hard functions and parallel graph pebbling

PRACTICALITIES

Lunch is served at 12:00 noon (register at this doodle at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

There is growing interest in the security community in Memory-Hard Functions (MHFs). These require moderate amounts of memory to compute on a general-purpose single-processor (i.e. sequential) machine, but cannot be *repeatedly* computed with significantly less memory amortized per instance on dedicated custom hardware (i.e. a *parallel* generalized circuit). For example, such functions are used for password-hashing and key-derivation to prevent brute-force attacks being cost-effectively implemented on custom circuits and in proofs-of-work for more egalitarian decentralized cryptocurrencies.

In (STOC 2015) Alwen and Serbinenko showed that, in order to construct a secure MHF it suffices to find a constant in-degree directed acyclic graph with a high cumulative pebbling complexity in a simple game of parallel pebbling. Conversely a wide class of candidate MHF constructions from the literature are given by fixing some particular (constant in-degree) DAG and showing an efficient way to pebble these DAGs immediately leads to a break of the MHF construction (i.e. a method of computing the MHF with low parallel memory complexity).

The first part of this talk will be aimed at providing an overview of this area of research. In particular will cover the following:

 - The motivation for and definition of MHFs.

 - The close connection to a certain parallel pebbling game over DAGs and new pebbling complexity measure called the cumulative complexity (CC) of the DAG.

 - What won't work: line graphs, bit-reversal graphs, superconcentrators and stacks of superconcentrators.

 - A powerful parallel pebbling algorithm with low CC. In particular we show how this gives us a non-trivial general lower-bound on the CC of any DAG of a fixed size.

 - A method for lower-bounding the CC of a DAG using a well-studied combinatorial property of the DAG called its depth-robustness.

- Finally we conclude with two strong positive results. Namely a pair of constant in-degree DAGs enjoying very high CC. Indeed the second has maximal CC for any constant in-degree DAG of equal size. Moreover it can be sequentially pebbled with this same CC. Thus we obtain a provably secure MHF.

To demonstrate the power of these tools we will also briefly describe their implications for several of the most important MHF candidate constructions from the literature including the winner and several of the finalists of the recent multi-year international Password Hashing Competition. For each candidate we will see an attack strongly invalidating the conjectured security of the construction. We will also see a (weak) security proof for the construction showing that the attack is (essentially) optimal.

The second part of this talk will focus on some of the most important proof techniques underlying these results. In particular we will cover the following:

 - The "meta-node" technique for analysing the CC of random DAGs.

 - A method for in-degree reduction in graphs.

 - Lower-bounding CC using depth-robustness.

 - Using the "dispersal" property of a graph to lower-bound its CC.

 - Stacks of depth-robust graphs with maximal parallel CC which can nevertheless be sequentially pebbled with the same CC.