Cryptology ePrint Archive: Report 2021/801

Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

Mohammad Hassan Ameri and Alexander R. Block and Jeremiah Blocki

Abstract: We introduce and construct memory-hard puzzles. Intuitively, a puzzle is memory-hard if it cannot be solved by any parallel random access machine (PRAM) algorithm with small (amortized) area-time complexity $t^{2-\varepsilon}$. The puzzles should also be easy to generate and should be solvable by a sequential PRAM algorithm running in total time $t$ and area-time complexity at most $t^2$. We construct memory-hard puzzles in the standard model using succinct randomized encodings (Bitansky et al., STOC 2015) under the minimal assumption that a memory-hard language exists. Intuitively, a language is memory-hard if it is undecidable by any PRAM algorithm with small (amortized) area-time complexity $t^{2 - \varepsilon}$ while the language can be decided in time $t$ and with area-time complexity at most $t^2$.

We give two applications which highlight the utility of memory-hard puzzles. For our first application, we give a construction of a (one-time) memory-hard function (MHF) in the standard model, using our memory-hard puzzles and additionally assuming indistinguishability obfuscation. Our construction is the first provable MHF in the standard model --- prior MHF constructions require idealized models (e.g., random oracle model) to prove security. For our second application, we show any cryptographic puzzle (e.g., memory-hard, time-lock) can be used to construct resource-bounded locally decodable codes (LDC) in the standard model, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020). Prior constructions required idealized primitives like random oracles and assuming that the encoding algorithm efficiency was not resource-constrained like the channel. In particular, assuming time-lock puzzles or memory-hard puzzles, we construct resource-bounded LDCs which are secure against low-depth channels or channels with small (amortized) area-time complexity, respectively.

Category / Keywords: foundations / memory-hard puzzles, cryptographic puzzles, memory-hard functions, resource-bounded locally decodably codes, randomized encodings