---
res:
  bibo_abstract:
  - 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Joel F
      foaf_name: Alwen, Joel F
      foaf_surname: Alwen
      foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Binchi
      foaf_name: Chen, Binchi
      foaf_surname: Chen
  - foaf_Person:
      foaf_givenName: Krzysztof Z
      foaf_name: Pietrzak, Krzysztof Z
      foaf_surname: Pietrzak
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9139-1654
  - foaf_Person:
      foaf_givenName: Leonid
      foaf_name: Reyzin, Leonid
      foaf_surname: Reyzin
  - foaf_Person:
      foaf_givenName: Stefano
      foaf_name: Tessaro, Stefano
      foaf_surname: Tessaro
  bibo_doi: 10.1007/978-3-319-56617-7_2
  bibo_volume: 10212
  dct_date: 2017^xs_gYear
  dct_identifier:
  - UT:000419175900002
  dct_isPartOf:
  - http://id.crossref.org/issn/978-331956616-0
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Scrypt is maximally memory hard@
...