---
_id: '635'
abstract:
- lang: eng
  text: Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is
    dominated by memory cost. As memory, unlike computation, costs about the same
    across different platforms, MHFs cannot be evaluated at significantly lower cost
    on dedicated hardware like ASICs. MHFs have found widespread applications including
    password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt,
    a simple candidate MHF designed by Percival, and described in RFC 7914. It has
    been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and
    has been an inspiration for Argon2d, one of the winners of the recent password-hashing
    competition. Despite its popularity, no rigorous lower bounds on its memory complexity
    are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative
    memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w
    and n are the output length and number of invocations of the underlying hash function,
    respectively. High cmc is a strong security target for MHFs introduced by Alwen
    and Serbinenko (STOC’15) which implies high memory cost even for adversaries who
    can amortize the cost over many evaluations and evaluate the underlying hash functions
    many times in parallel. Our proof is the first showing optimal memory-hardness
    for any MHF. Our result improves both quantitatively and qualitatively upon the
    recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of
    Ω(n2w/ log2 n) for a restricted class of adversaries.
alternative_title:
- LNCS
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: Binchi
  full_name: Chen, Binchi
  last_name: Chen
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Leonid
  full_name: Reyzin, Leonid
  last_name: Reyzin
- first_name: Stefano
  full_name: Tessaro, Stefano
  last_name: Tessaro
citation:
  ama: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory
    hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:<a
    href="https://doi.org/10.1007/978-3-319-56617-7_2">10.1007/978-3-319-56617-7_2</a>'
  apa: 'Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., &#38; Tessaro, S. (2017).
    Scrypt is maximally memory hard. In J.-S. Coron &#38; J. Buus Nielsen (Eds.) (Vol.
    10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic
    Techniques, Paris, France: Springer. <a href="https://doi.org/10.1007/978-3-319-56617-7_2">https://doi.org/10.1007/978-3-319-56617-7_2</a>'
  chicago: Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano
    Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and
    Jesper Buus Nielsen, 10212:33–62. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-56617-7_2">https://doi.org/10.1007/978-3-319-56617-7_2</a>.
  ieee: 'J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt
    is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications
    of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.'
  ista: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally
    memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
    vol. 10212, 33–62.'
  mla: Alwen, Joel F., et al. <i>Scrypt Is Maximally Memory Hard</i>. Edited by Jean-Sébastien
    Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:<a href="https://doi.org/10.1007/978-3-319-56617-7_2">10.1007/978-3-319-56617-7_2</a>.
  short: J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron,
    J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.
conference:
  end_date: 2017-05-04
  location: Paris, France
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2017-04-30
date_created: 2018-12-11T11:47:37Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-09-11T07:24:51Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-56617-7_2
ec_funded: 1
editor:
- first_name: Jean-Sébastien
  full_name: Coron, Jean-Sébastien
  last_name: Coron
- first_name: Jesper
  full_name: Buus Nielsen, Jesper
  last_name: Buus Nielsen
external_id:
  isi:
  - '000419175900002'
fulldoi: https://doi.org/10.1007/978-3-319-56617-7_2
intvolume: '     10212'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2016/989
month: '01'
oa: 1
oa_version: Submitted Version
page: 33 - 62
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication_identifier:
  isbn:
  - 978-331956616-0
publication_status: published
publisher: Springer
publist_id: '7154'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scrypt is maximally memory hard
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10212
year: '2017'
...