Paper 2014/238
High Parallel Complexity Graphs and MemoryHard Functions
Joël Alwen and Vladimir Serbinenko
Abstract
We develop new theoretical tools for proving lowerbounds on the (amortized) complexity of functions in a parallel setting. We demonstrate their use by constructing the first provably secure Memoryhard functions (MHF); a class of functions recently gaining acceptance in practice as an effective means to counter bruteforce 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 lowerbounds 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 nontibial proof, an explicit construction of a constant indegree 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 Memoryhard 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/FPGAresistant proofsofwork of the cryptocurrency Litecoin\cite{Litecoin}, the bruteforce resistant keyderivation 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.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 PebblingGraph ComplexityParallelismCryptographyMemoryHard Functions
 Contact author(s)
 jalwen @ ist ac at
 History
 20141104: revised
 20140411: received
 See all versions
 Short URL
 https://ia.cr/2014/238
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/238, author = {Joël Alwen and Vladimir Serbinenko}, title = {High Parallel Complexity Graphs and MemoryHard Functions}, howpublished = {Cryptology ePrint Archive, Paper 2014/238}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/238}}, url = {https://eprint.iacr.org/2014/238} }