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 boundedmore »
MemoryHard Puzzles in the Standard Model with Applications to MemoryHard Functions and ResourceBounded Locally Decodable Codes
We formally introduce, define, and construct {\em memoryhard puzzles}. Intuitively, for a difficulty parameter $t$, a cryptographic puzzle is memoryhard if any parallel random access machine (PRAM) algorithm with ``small'' cumulative memory complexity ($\ll t^2$) cannot solve the puzzle; moreover, such puzzles should be both ``easy'' to generate and be solvable by a sequential RAM algorithm running in time $t$. Our definitions and constructions of memoryhard puzzles are in the standard model, assuming the existence of indistinguishability obfuscation (\iO) and oneway functions (OWFs), and additionally assuming the existence of a {\em memoryhard language}.
Intuitively, a language is memoryhard if it is undecidable by any PRAM algorithm with ``small'' cumulative memory complexity, while a sequential RAM algorithm running in time $t$ can decide the language. Our definitions and constructions of memoryhard objects are the first such definitions and constructions in the standard model without relying on idealized assumptions (such as random oracles).
We give two applications which highlight the utility of memoryhard puzzles. For our first application, we give a construction of a (onetime) {\em memoryhard function} (MHF) in the standard model, using memoryhard puzzles and additionally assuming \iO and OWFs. For our second application, we show any cryptographic puzzle (\eg, memoryhard, timelock) more »
 Publication Date:
 NSFPAR ID:
 10340397
 Journal Name:
 Security and Cryptography for Networks
 Sponsoring Org:
 National Science Foundation
More Like this


Errorcorrecting codes that admit {\em local} decoding and correcting algorithms have been the focus of much recent research due to their numerous theoretical and practical applications. An important goal is to obtain the best possible tradeoffs between the number of queries the algorithm makes to its oracle (the {\em locality} of the task), and the amount of redundancy in the encoding (the {\em information rate}). In Hamming's classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality, but superpolynomial blocklength, or small blocklength, but high locality. However, in the computationally bounded, adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions e.g., Ostrovsky, Pandey and Sahai (ICALP 2007) construct private locally decodable codes in the setting where the sender and receiver already share a symmetric key. We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no publickey or privatekey cryptographic setup. The only setup assumption we require is the selection of the {\em public} parameters (seed) for a collisionresistant hash function. Specifically, we provide constructions of {\em relaxed locallymore »

Memoryhard functions (MHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work. Over the past few years several increasingly stringent goals for an MHF have been proposed including the requirement that the MHF have high sequential spacetime (ST) complexity, parallel spacetime complexity, amortized areatime (aAT) complexity and sustained space complexity. DataIndependent Memory Hard Functions (iMHFs) are of special interest in the context of password hashing as they naturally resist sidechannel attacks. iMHFs can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree and the complexity of the iMHF can be analyzed using a pebbling game. Recently, Alwen et al. [CCS'17] constructed an DAG called DRSample which has aAT complexity at least $\Omega\left( N^2/\log N\right)$. Asymptotically DRSample outperformed all prior iMHF constructions including Argon2i, winner of the password hashing competition (aAT cost $\mathcal{O}\left(N^{1.767}\right)$), though the constants in these bounds are poorly understood. We show that the the greedy pebbling strategy of Boneh et al. [ASIACRYPT'16] is particularly effective against DRSample e.g., the aAT cost is $\mathcal{O}\left( N^2/\log N\right)$. In fact, our empirical analysis {\em reverses} the prior conclusion of Alwen et al. that DRSample providesmore »

Yael Tauman Kalai and Adam D. Smith and Daniel Wichs (Ed.)Constructions of locally decodable codes (LDCs) have one of two undesirable properties: low rate or high locality (polynomial in the length of the message). In settings where the encoder/decoder have already exchanged cryptographic keys and the channel is a probabilistic polynomial time (PPT) algorithm, it is possible to circumvent these barriers and design LDCs with constant rate and small locality. However, the assumption that the encoder/decoder have exchanged cryptographic keys is often prohibitive. We thus consider the problem of designing explicit and efficient LDCs in settings where the channel is slightly more constrained than the encoder/decoder with respect to some resource e.g., space or (sequential) time. Given an explicit function f that the channel cannot compute, we show how the encoder can transmit a random secret key to the local decoder using f(⋅) and a random oracle 𝖧(⋅). We then bootstrap the private key LDC construction of Ostrovsky, Pandey and Sahai (ICALP, 2007), thereby answering an open question posed by Guruswami and Smith (FOCS 2010) of whether such bootstrapping techniques are applicable to LDCs in channel models weaker than just PPT algorithms. Specifically, in the random oracle model we show how to construct explicit constant rate LDCs with locality ofmore »

The cumulative pebbling complexity of a directed acyclic graph G is defined as cc(G) = min_P ∑_i P_i, where the minimum is taken over all legal (parallel) black pebblings of G and P_i denotes the number of pebbles on the graph during round i. Intuitively, cc(G) captures the amortized SpaceTime complexity of pebbling m copies of G in parallel. The cumulative pebbling complexity of a graph G is of particular interest in the field of cryptography as cc(G) is tightly related to the amortized AreaTime complexity of the DataIndependent MemoryHard Function (iMHF) f_{G,H} [Joël Alwen and Vladimir Serbinenko, 2015] defined using a constant indegree directed acyclic graph (DAG) G and a random oracle H(⋅). A secure iMHF should have amortized SpaceTime complexity as high as possible, e.g., to deter bruteforce password attacker who wants to find x such that f_{G,H}(x) = h. Thus, to analyze the (in)security of a candidate iMHF f_{G,H}, it is crucial to estimate the value cc(G) but currently, upper and lower bounds for leading iMHF candidates differ by several orders of magnitude. Blocki and Zhou recently showed that it is NPHard to compute cc(G), but their techniques do not even rule out an efficient (1+ε)approximation algorithmmore »