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 formally introduce, define, and construct memory-hard puzzles. Intuitively, for a difficulty parameter $t$, a cryptographic puzzle is memory-hard if any parallel random access machine (PRAM) algorithm with "small" (amortized) area-time 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 memory-hard puzzles are in the standard model, assuming the existence of indistinguishability obfuscation ($i\mathcal{O}$) and one-way functions (OWFs), and additionally assuming the existence of a memory-hard language. Intuitively, a language is memory-hard if it is undecidable by any PRAM algorithm with "small" (amortized) area-time complexity, while a sequential RAM algorithm running in time $t$ can decide the language. Our definitions and constructions of memory-hard 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 memory-hard puzzles. For our first application, we give a construction of a (one-time) memory-hard function (MHF) in the standard model, using memory-hard puzzles and additionally assuming $i\mathcal{O}$ and OWFs. 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 (LDCs) in the standard model, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020). Resource-bounded LDCs achieve better rate and locality than their classical counterparts under the assumption that the adversarial channel is resource bounded e.g., a low-depth circuit. Prior constructions of MHFs and resource-bounded LDCs required idealized primitives like random oracles.

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

Date: received 12 Jun 2021, last revised 21 Sep 2021

Contact author: block9 at purdue edu

Available format(s): PDF | BibTeX Citation

Version: 20210921:201734 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]