International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Memory-Hard Functions from Cryptographic Primitives

Binyi Chen
Stefano Tessaro
DOI: 10.1007/978-3-030-26951-7_19
Search ePrint
Search Google
Abstract: Memory-hard functions (MHFs) are moderately-hard functions which enforce evaluation costs both in terms of time and memory (often, in form of a trade-off). They are used e.g. for password protection, password-based key-derivation, and within cryptocurrencies, and have received a considerable amount of theoretical scrutiny over the last few years. However, analyses see MHFs as modes of operation of some underlying hash function $$\mathcal {H}$$, modeled as a monolithic random oracle. This is however a very strong assumption, as such hash functions are built from much simpler primitives, following somewhat ad-hoc design paradigms.This paper initiates the study of how to securely instantiate $$\mathcal {H}$$ within MHF designs using common cryptographic primitives like block ciphers, compression functions, and permutations. Security here will be in a model in which the adversary has parallel access to an idealized version of the underlying primitive. We will provide provably memory-hard constructions from all the aforementioned primitives. Our results are generic, in that we will rely on hard-to-pebble graphs designed in prior works to obtain our constructions.One particular challenge we encounter is that $$\mathcal {H}$$ is usually required to have large outputs (to increase memory hardness without changing the description size of MHFs), whereas the underlying primitives generally have small output sizes.
  title={Memory-Hard Functions from Cryptographic Primitives},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Binyi Chen and Stefano Tessaro},