Author(s):

Alwen, Joël; Serbinenko, Vladimir

Title: 
High parallel complexity graphs and memoryhard functions

Affiliation 
IST Austria 
Abstract: 
We develop new theoretical tools for proving lowerbounds 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 MemoryHard Functions (MHF); a security primitive which has recently been gaining acceptance in practice as an effective means of countering bruteforce 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 indegree 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 lowerbound 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; MemoryHard Functions

Conference Title:

STOC: Symposium on the Theory of Computing

Conference Dates:

June 1517, 2015

Conference Location:

Portland, OR, USA

ISBN:

9781450335362

Publisher:

ACM

Date Published:

20150601

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 (259668PSPC).

URL: 

DOI: 
10.1145/2746539.2746622

Open access: 
yes (repository) 