# High parallel complexity graphs and memory-hard functions

Alwen JF, Serbinenko V. 2015. High parallel complexity graphs and memory-hard functions. Proceedings of the 47th annual ACM symposium on Theory of computing. STOC: Symposium on the Theory of Computing, 595–603.

Download (ext.)

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Alwen, Joel F

^{ISTA}; Serbinenko, VladimirDepartment

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.

Publishing Year

Date Published

2015-06-01

Proceedings Title

Proceedings of the 47th annual ACM symposium on Theory of computing

Page

595 - 603

Conference

STOC: Symposium on the Theory of Computing

Conference Location

Portland, OR, United States

Conference Date

2015-06-14 – 2015-06-17

IST-REx-ID

### Cite this

Alwen JF, Serbinenko V. High parallel complexity graphs and memory-hard functions. In:

*Proceedings of the 47th Annual ACM Symposium on Theory of Computing*. ACM; 2015:595-603. doi:10.1145/2746539.2746622Alwen, J. F., & Serbinenko, V. (2015). High parallel complexity graphs and memory-hard functions. In

*Proceedings of the 47th annual ACM symposium on Theory of computing*(pp. 595–603). Portland, OR, United States: ACM. https://doi.org/10.1145/2746539.2746622Alwen, Joel F, and Vladimir Serbinenko. “High Parallel Complexity Graphs and Memory-Hard Functions.” In

*Proceedings of the 47th Annual ACM Symposium on Theory of Computing*, 595–603. ACM, 2015. https://doi.org/10.1145/2746539.2746622.J. F. Alwen and V. Serbinenko, “High parallel complexity graphs and memory-hard functions,” in

*Proceedings of the 47th annual ACM symposium on Theory of computing*, Portland, OR, United States, 2015, pp. 595–603.Alwen, Joel F., and Vladimir Serbinenko. “High Parallel Complexity Graphs and Memory-Hard Functions.”

*Proceedings of the 47th Annual ACM Symposium on Theory of Computing*, ACM, 2015, pp. 595–603, doi:10.1145/2746539.2746622.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access