Paper 2014/238

High Parallel Complexity Graphs and Memory-Hard Functions

Joël Alwen and Vladimir Serbinenko

Abstract

We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of functions in a parallel setting. We demonstrate their use by constructing the first provably secure Memory-hard functions (MHF); a class of functions recently gaining acceptance in practice as an effective means to counter brute-force attacks on security relevant functions. Pebbling games over graphs have proven to be a powerful abstraction for a wide variety of computational models. A dominant application of such games is proving complexity lower-bounds using ``pebbling reductions''. These bound the complexity of a given function $f_G$ in some computational model $\M$ of interest in terms of the pebbling complexity of a related graph $G$, where the pebbling complexity is defined via a pebbling game $\G$. In particular, finding a function with high complexity in $\M$ is reduced to (the hopefully simpler task of) finding graphs with high pebbling complexity in $\G$. We introduce a very simple and natural pebbling game $\G_p$ for abstracting parallel computation models. As an important conceptual contribution we also define a natural measure of pebbling complexity called \emph{cumulative complexity} (CC) and show how it overcomes a crucial shortcoming in the parallel setting exhibited by more traditional complexity measures used in past reductions. Next (analogous to the results of Tarjan et. al.~\cite{PTC77,LT82} for sequential pebbling games) we demonstrates, via a novel and non-tibial proof, an explicit construction of a constant in-degree family of graphs whose CC in $\G_p$ approaches maximality to within a polylogarithmic factor for any graph of equal size. To demonstrate the use of these theoretical tools we give an example in the field of cryptography, by constructing the first provably secure Memory-hard function (MHF). Introduced by Percival~\cite{Per09}, an MHF can be computed efficiently on a sequential machine but further requires the same amount of memory (or much greater time) amortized per evaluation on a parallel machine. Thus, while a say an ASIC or FPGA may be faster than a CPU, the increased cost of working memory negates this advantage. In particular MHFs crucially underly the ASIC/FPGA-resistant proofs-of-work of the crypto-currency Litecoin\cite{Litecoin}, the brute-force resistant key-derivation function {\tt scrypt}~\cite{Per09} and can be used to increase the cost to an adversary of recovering passwords from a compromised login server. To place these applications on more sound theoretic footing we first provide a new formal definition (in the Random Oracle Model) and an accompanying notion of amortized memory hardness to capture the intuitive property of an MHF (thereby remedying an important issue with the original definition of~\cite{Per09}). Next we define a mapping from a graph $G$ to a related function $f_G$. Finally we prove a pebbling reduction bounding the amortized memory hardness per evaluation of $f_G$ in terms of the CC of $G$ in the game $\G_p$. Together with the construction above, this gives rise to the first provably secure example of an MHF.

Note: Added intuition to and fixed typos in the proof of Theorem 1. Revised the motivation justifying the amortized complexity notion in the pROM. Formalized (and showed how to construct) an MHF in the pROM.