Abstract
Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive keyderivation functions resistant to bruteforce attacks. Broadly speaking, MHFs can be divided into two categories: datadependent memory hard functions (dMHFs) and dataindependent memory hard functions (iMHFs). iMHFs are resistant to certain sidechannel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive input e.g., password. While dMHFs are potentially vulnerable to sidechannel attacks (the induced memory access pattern might leak useful information to a bruteforce attacker), they can achieve higher cumulative memory complexity (CMC) in comparison than an iMHF. In particular, any iMHF that can be evaluated in N steps on a sequential machine has CMC at most 𝒪((N^2 log log N)/log N). By contrast, the dMHF scrypt achieves maximal CMC Ω(N^2)  though the CMC of scrypt would be reduced to just 𝒪(N) after a sidechannel attack.
In this paper, we introduce the notion of computationally dataindependent memory hard functions (ciMHFs). Intuitively, we require that memory access pattern induced by the (randomized) ciMHF evaluation algorithm appears to be independent from the standpoint of a computationally bounded eavesdropping attacker  even if the attacker selects the initial input. We then ask whether it is possible to circumvent known upper bound for iMHFs and build a ciMHF with CMC Ω(N^2). Surprisingly, we answer the question in the affirmative when the ciMHF evaluation algorithm is executed on a twotiered memory architecture (RAM/Cache).
We introduce the notion of a krestricted dynamic graph to quantify the continuum between unrestricted dMHFs (k=n) and iMHFs (k=1). For any ε > 0 we show how to construct a krestricted dynamic graph with k=Ω(N^(1ε)) that provably achieves maximum cumulative pebbling cost Ω(N^2). We can use krestricted dynamic graphs to build a ciMHF provided that cache is large enough to hold k hash outputs and the dynamic graph satisfies a certain property that we call "amenable to shuffling". In particular, we prove that the induced memory access pattern is indistinguishable to a polynomial time attacker who can monitor the locations of read/write requests to RAM, but not cache. We also show that when k=o(N^(1/log log N)) , then any krestricted graph with constant indegree has cumulative pebbling cost o(N^2). Our results almost completely characterize the spectrum of krestricted dynamic graphs.
BibTeX  Entry
@InProceedings{ameri_et_al:LIPIcs:2020:11721,
author = {Mohammad Hassan Ameri and Jeremiah Blocki and Samson Zhou},
title = {{Computationally DataIndependent Memory Hard Functions}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {36:136:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11721},
URN = {urn:nbn:de:0030drops117214},
doi = {10.4230/LIPIcs.ITCS.2020.36},
annote = {Keywords: Computationally DataIndependent Memory Hard Function, Cumulative Memory Complexity, Dynamic Pebbling Game}
}
Keywords: 

Computationally DataIndependent Memory Hard Function, Cumulative Memory Complexity, Dynamic Pebbling Game 
Collection: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

06.01.2020 