---
_id: '1652'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
author:
- first_name: Joel F
  full_name: Alwen, Joel F
  id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  last_name: Alwen
- first_name: Vladimir
  full_name: Serbinenko, Vladimir
  last_name: Serbinenko
citation:
  ama: 'Alwen JF, Serbinenko V. High parallel complexity graphs and memory-hard functions.
    In: <i>Proceedings of the 47th Annual ACM Symposium on Theory of Computing</i>.
    ACM; 2015:595-603. doi:<a href="https://doi.org/10.1145/2746539.2746622">10.1145/2746539.2746622</a>'
  apa: 'Alwen, J. F., &#38; Serbinenko, V. (2015). High parallel complexity graphs
    and memory-hard functions. In <i>Proceedings of the 47th annual ACM symposium
    on Theory of computing</i> (pp. 595–603). Portland, OR, United States: ACM. <a
    href="https://doi.org/10.1145/2746539.2746622">https://doi.org/10.1145/2746539.2746622</a>'
  chicago: Alwen, Joel F, and Vladimir Serbinenko. “High Parallel Complexity Graphs
    and Memory-Hard Functions.” In <i>Proceedings of the 47th Annual ACM Symposium
    on Theory of Computing</i>, 595–603. ACM, 2015. <a href="https://doi.org/10.1145/2746539.2746622">https://doi.org/10.1145/2746539.2746622</a>.
  ieee: J. F. Alwen and V. Serbinenko, “High parallel complexity graphs and memory-hard
    functions,” in <i>Proceedings of the 47th annual ACM symposium on Theory of computing</i>,
    Portland, OR, United States, 2015, pp. 595–603.
  ista: '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.'
  mla: Alwen, Joel F., and Vladimir Serbinenko. “High Parallel Complexity Graphs and
    Memory-Hard Functions.” <i>Proceedings of the 47th Annual ACM Symposium on Theory
    of Computing</i>, ACM, 2015, pp. 595–603, doi:<a href="https://doi.org/10.1145/2746539.2746622">10.1145/2746539.2746622</a>.
  short: J.F. Alwen, V. Serbinenko, in:, Proceedings of the 47th Annual ACM Symposium
    on Theory of Computing, ACM, 2015, pp. 595–603.
conference:
  end_date: 2015-06-17
  location: Portland, OR, United States
  name: 'STOC: Symposium on the Theory of Computing'
  start_date: 2015-06-14
corr_author: '1'
cryptoeprintid: 1
das_tickbox: '1'
date_created: 2018-12-11T11:53:16Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2026-06-22T14:08:55Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/2746539.2746622
ec_funded: 1
external_id:
  cryptoeprintid:
  - 2014/238
  isi:
  - '000485296600063'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://eprint.iacr.org/2014/238
month: '06'
oa: 1
oa_version: Submitted Version
page: 595 - 603
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication: Proceedings of the 47th annual ACM symposium on Theory of computing
publication_status: published
publisher: ACM
publist_id: '5498'
quality_controlled: '1'
scopus_import: '1'
status: public
title: High parallel complexity graphs and memory-hard functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...