Welcome to the resource topic for 2014/238
Title:
High Parallel Complexity Graphs and Memory-Hard Functions
Authors: Joël Alwen, 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.
ePrint: https://eprint.iacr.org/2014/238
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .