High parallel complexity graphs and memory-hard functions Conference Paper

Author(s): Alwen, Joël; Serbinenko, Vladimir
Title: High parallel complexity graphs and memory-hard functions
Affiliation IST Austria
Abstract: We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of certain functions in models of parallel computation. We apply the tools to construct a class of functions with high amortized memory complexity in the parallel Random Oracle Model (pROM); a variant of the standard ROM allowing for batches of simultaneous queries. In particular we obtain a new, more robust, type of Memory-Hard Functions (MHF); a security primitive which has recently been gaining acceptance in practice as an effective means of countering brute-force attacks on security relevant functions. Along the way we also demonstrate an important shortcoming of previous definitions of MHFs and give a new definition addressing the problem. The tools we develop represent an adaptation of the powerful pebbling paradigm (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73]) to a simple and intuitive parallel setting. We define a simple pebbling game Gp over graphs which aims to abstract parallel computation in an intuitive way. As a conceptual contribution we define a measure of pebbling complexity for graphs called cumulative complexity (CC) and show how it overcomes a crucial shortcoming (in the parallel setting) exhibited by more traditional complexity measures used in the past. As a main technical contribution we give an explicit construction of a constant in-degree family of graphs whose CC in Gp approaches maximality to within a polylogarithmic factor for any graph of equal size (analogous to the graphs of Tarjan et. al. [PTC76, LT82] for sequential pebbling games). Finally, for a given graph G and related function fG, we derive a lower-bound on the amortized memory complexity of fG in the pROM in terms of the CC of G in the game Gp.
Keywords: Cryptography; Pebbling; Graph Complexity; Parallelism; Memory-Hard Functions
Conference Title: STOC: Symposium on the Theory of Computing
Conference Dates: June 15-17, 2015
Conference Location: Portland, OR, USA
ISBN: 978-145033536-2
Publisher: ACM  
Date Published: 2015-06-01
Start Page: 595
End Page: 603
Sponsor: This work of the first author was also partly funded by the European Research Council under an ERC Starting Grant (259668-PSPC).
DOI: 10.1145/2746539.2746622
Open access: yes (repository)
IST Austria Authors
  1. Joel Alwen
    13 Alwen
Related IST Austria Work