Paper 2016/989
Scrypt is Maximally Memory-Hard
Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro
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
Note: Clarifications and minor fixes from previous versions.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- scryptmemory-hard functionspassword hashing
- Contact author(s)
- reyzin @ cs bu edu
- History
- 2016-12-21: revised
- 2016-10-17: received
- See all versions
- Short URL
- https://ia.cr/2016/989
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/989, author = {Joël Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro}, title = {Scrypt is Maximally Memory-Hard}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/989}, year = {2016}, url = {https://eprint.iacr.org/2016/989} }