  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 key-derivation functions resistant to brute-force attacks.
Broadly speaking, MHFs can be divided into two categories: data-dependent
memory hard functions (dMHFs) and data-independent memory hard functions
(iMHFs). iMHFs are resistant to certain side-channel 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 side-channel attacks (the induced memory access pattern might
leak useful information to a brute-force attacker), they can achieve higher
cumulative memory complexity (CMC) in comparison than an iMHF. In this paper,
we introduce the notion of computationally data-independent 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
$\Omega(N^2)$. Surprisingly, we answer the question in the affirmative when the
ciMHF evaluation algorithm is executed on a two-tiered memory architecture
(RAM/Cache).
  See paper for the full abstract.
