---
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_isPartOf:
- http://id.crossref.org/issn/978-331956616-0
dct_language: eng
dct_publisher: Springer@
dct_title: Scrypt is maximally memory hard@
...