You are looking at a specific version 20210614:135020 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
memory-hard puzzlescryptographic puzzlesmemory-hard functionsresource-bounded locally decodably codesrandomized encodings
Contact author(s)
block9 @ purdue edu
History
2022-05-02: last of 2 revisions
2021-06-14: received
See all versions
Short URL
https://ia.cr/2021/801
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.